Бинарный поиск (binary_search, lower_bound, upper_bound)

binary_search
Формулировка задачи: Узнать, находится ли данный элемент в отсортированном массиве подобных элементов, для которых задано отношение порядка на множестве. Т.е. имея в наличии два элемента, можно однозначно определить операцию <. Сложность O(log(N)).
Реализация:

1. bool binary_search(const vector<int> &mas, const int &value)
2. {
3.   int l = 0, r = mas.size()-1;
4.   while (l<r)
5.   {
6.     int m = (l+r)>>1;
7.     if (mas[m] < value)
8.       l = m +1;
9.     else if (mas[m] > value)
10.       r = m - 1;
11.     else
12.       return true;
13.   }
14.   return mas[l] == value;
15. }

* This source code was highlighted with Source Code Highlighter.

lower_bound
Формулировка задачи: В отсортированном массиве найти позицию самого левого вхождения заданного элемента. Если элемента в в массиве нет, то вернуть –1. Сложность O(log(N)).
Реализация:

1. int lower_bound(const vector<int> &mas, const int &value)
2. {
3.   int l = 0, r = mas.size() - 1;
4.   while (l < r)
5.   {
6.     int m = l + (r - l)/2;
7.     if (mas[m] >= value)
8.       r = m;
9.     else
10.       l = m + 1;
11.   }
12.   return mas[l] == value ? l : -1;
13. }

* This source code was highlighted with Source Code Highlighter.

upper_bound
Формулировка задачи: В отсортированном массиве найти позицию самого правого вхождения заданного элемента. Если элемента в массиве нет, то вернуть –1. Сложность O(log(N)).
Реализация:

1. int upper_bound (const vector<int> &mas, const int &value)
2. {
3.   int l = 0, r = mas.size() - 1;
4.   while (l < r)
5.   {
6.     int m = r - (r - l)/2;
7.     if (mas[m] <= value)
8.       l = m;
9.     else
10.       r = m - 1;
11.   }
12.   return mas[l] == value ? l : -1;
13. }

* This source code was highlighted with Source Code Highlighter.