среда, 28 июля 2010 г.

Бинарный поиск (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.

3 комментария:

  1. Предлагаю везде добавить квалификаторы const vector & mas

    ОтветитьУдалить
  2. это было бы неплохо. В обозримом будущем предложу другую реализацию. Более интуитивно понятную

    ОтветитьУдалить
  3. По просьбе трудящихся переписал lower_bound и upper_bound на более интутивнопонятные реализации

    ОтветитьУдалить