Бинарный поиск в отсортированных данных

Алгоритмы   1 Апрель 2012  Автор статьи:  

В массиве неотсортированных данных при отсутствии дополнительных фактов, поиск элемента по ключу осуществляется за O(n). В отсортированных данных возможно применение двоичного(бинарного поиска), который позволяет найти элемент по ключу за O(log(n)).
Общая стратегия бинарного поиска
Если данные отсортированы по неубыванию ключа, а поиск осуществляется на отрезке [l..r] массива а, то сравнив искомое значение х с а[mid], где mid = (l+r)/2, можно сделать вывод: в левой или правой части от mid находится искомое значение. С помощью одной проверки, размер области поиска уменьшается в два раза и следовательно, размер области поиска достигнет минимального значения(длина отрезка [l..r] равна 1) через \log_2{n} шагов, где n — первоначальный размер области поиска. В большинстве языков программирования функция бинарного поиска является стандартной
Модификации функции бинарного поиска
Первое вхождение элемента(first index off)
Как ясно из названия, функция находит первое вхождение элемента х в массив. В языках программирования, стандартный бинарный поиск находит как раз первое вхождение элемента х в массив.
Алгоритм(на вход подается нам массив а размерности n и искомое значение х):

  1. Берем l=0 и r=n-1
  2. Берем mid = l+(r-l)/2 (можно было бы взять и (l+r)/2, но в некоторых случаях это может привести к переполнению типа данных
  3. Если a[mid]
  4. Возвращаемся к шагу 2, если длина отрезка [l..r]больше 1.
  5. На отрезке [l..r] поэлементным перебором ищем первое вхождение элемента х. Если такого элемента нет, возвращаем -1

При выполнении этого алгоритма верно утверждение: если в массиве а есть элемент, равный х, то позиция первого такого элемента будет всегда содержаться в отрезке [l..r]. Если mid не попадает в значение, равное х, то очевидно, утверждение верно, а если mid попадает в значение, равное х, то переход осуществляется таким образом, что первое из значений х остается в отрезке [l..r].
Последнее вхождение элемента(last index of)
Эта функция находит точно последнее вхождение вхождение элемента х в массив а. Алгоритм функции практически аналогичен алгоритму предыдущей функции.
Алгоритм(на вход подается нам массив а размерности n и искомое значение х):

  1. Берем l=0 и r=n-1
  2. Берем mid = l+(r-l)/2 (можно было бы взять и (l+r)/2, но в некоторых случаях это может привести к переполнению типа данных
  3. Если a[mid]<=x, то l=mid; в противном случае r = mid
  4. Возвращаемся к шагу 2, если длина отрезка [l..r]больше 1.
  5. На отрезке [l..r] поэлементным перебором, начиная с r(т.е. идем в обратном порядке), ищем первое вхождение элемента х. Если такого элемента нет, возвращаем -1

Отрезок вхождения в массиве (equal range)
Данная функции возвращает отрезок массива [l..r]. где индексу l соответствует первое вхождение элемента х в массив а, a r — последнему вхождению элемента х. Очевидно, что алгоритм функции состоит в последовательном вызове функций первого и последнего вхождения элемента х и возвращении непосредственно отрезка[l..r].
Так как традиционный бинарный поиск на больших массивах практически не не использует кэш процессора,применяют следующую модификацию бинарного поиска, позволяющую эффективнее использовать кэш процессора:

  1. Пусть k=\sqrt{n}
  2. Выпишем в массив b каждый k-ый элемент массива а. Длина массива b составит примерно \sqrt{n}
  3. На массиве b найдем с помощью бинарного поиска значение b[i] такое, что b[i]\lex, но при этом i — максимально. Отрезок массива а [a\cdot{k}..i\cdot{k}+k-1] будет содержать элемент х, если он существует в массиве а
  4. На этом отрезке длины \sqrt{n} с помощью бинарного поиска находим искомое вхождение.

В этом алгоритме вместо одного бинарного поиска размерности n, производятся два бинарных поиска размерности \sqrt{n}, что лучше использует кэш, что следовательно может оказаться эффективнее.
В заключение следует отметить, что все выше перечисленные функции работают за O(log(n)). В следствие такой сложности, эти функции не проверяют,задан ли отсортированный массив или нет(на неотсортированном массиве бинарный поиск бесполезен), поэтому передачу в функции непосредственно отсортированных данных должен гарантировать сам программист.

Научиться программировать

  • на Delphi

  • на Java

  • на C++