Pull to refresh

Как же все-таки правильно написать двоичный поиск?

Algorithms
В обсуждениях статьи Только 10% программистов способны написать двоичный поиск так никто и не написал, как же правильно подойти к решению этой задачи.
Если мы не хотим использовать циклический метод «гадание, затем тестирование, затем исправление ошибок», то без инварианта цикла здесь не обойтись.
Инвариант цикла – это соотношение, которое истинно перед циклом, истинно в процессе выполнения цикла и истинно при выходе из цикла. Все это описано у Дейкстры в книге «Дисциплина программирования», и детально разжевано у Гриса в книге «Наука программирования». Тем не менее, по моим наблюдениям, на практике этот метод практически НИКТО не использует, считая, что все это к реальности не имеет никакого отношения. Это большая ошибка.

Сам Бентли c. 51 приводит такой инвариант: «если элемент T вообще есть в массиве X[1..N], то он должен быть в некоторой области, принадлежащей X». Первоначально эта область – весь массив.
Формулировка эта — довольно невнятная. Думаю, причина этого в том, что у Бентли мало опыта – он, как и многие, использует всю это теорию только для обучения, а не для реальной жизни.
Когда я читал книгу Бентли (давно) и дошел до слов «Чтобы вы поверили этому – отложите прямо сейчас эту книгу и попытайтесь написать программу сами» – я прикрыл книгу и довольно быстро нашел нормальную формулировку.
Определим по краям массива область О так, чтобы она не содержала искомый элемент T. Это и будет инвариантом цикла: «в области О не содержится искомый элемент T».
Первоначально эта область состоит из двух несмежных кусков нулевой длины (толщины, если угодно) в начале и в конце массива. Она не содержит искомый элемент, т. к. пуста и вообще ничего не содержит.
Если в процессе работы эта область покроет весь массив, то искомого элемента в массиве нет.

Формальная запись (буквы и размерность массива 1..N как у Бентли):
Aj: 1 <=j < L или U < j <= N: X[j] != T
Первоначально L=1, U=N, область пуста.
Когда область покроет весь массив? Когда L > U, можно нарисовать и проверить по клеточкам. Это условие будет использовано для выхода из цикла.

Теперь о содержимом цикла. Предположим, средний элемент (обозначим его индекс как M) массива X не равен искомому элементу T. Как мы можем изменить L и U так, чтобы инвариант остался истинным? В такой постановке задача оказывается настолько простой, что здесь негде ошибиться. Если T больше среднего элемента, то во всем куске от 1 до среднего элемента нет T. Аналогично, если T меньше среднего элемента, то во всем куске от среднего элемента до N нет T. Область расширяется, в первом случае L:=M+1, во втором U:=M-1.

Обратите внимание, что все основные моменты алгоритма, а именно: условие «L>U» для выхода из цикла (отрицание «L<=U» — для продолжения), изменение границ области L:=M+1, U:=M-1 мы вывели не гаданием, а строгими, при этом очень простыми рассуждениями.

Вот результирующий алгоритм на псевдокоде:

L := 1; U := N; found := false; 
while (L <= U) & not found do 
  M := середина отрезка L..U; 
  if a[M] = T then
    found := true;
  elseif a[M] < T then
    L := M+1;
  else
    U := M-1;
  end;
end
Tags:двоичный поискалгоритмы поиска
Hubs: Algorithms
Total votes 41: ↑30 and ↓11+19
Views12K

Popular right now

Top of the last 24 hours