Алгоритм дихотомического поиска

Дихотомический поиск значительно быстрее, чем линейный поиск, который заключается в том, чтобы сравнивать с элементами в списке последовательно, если только список не очень короткий или если искомый элемент находится во главе списка, что обычно не предсказуемо.

Этот алгоритм работает на упорядоченном наборе и использует приказ для управления поиском. Слово дихотомия происходит от греческого διχοτόμηση что означает: разрезать пополам.

Язык C++ обеспечивает binary_search функцию в библиотеке STL.
У . NET Framework аналогичные функции в базовых библиотеках (System.Array).
Приведенный ниже общий код не должен вызывать проблем в других языках программирования.

Принцип алгоритма

Как быстро найти слово Untel в словаре? Открываем книгу посередине и попадаешь на слова, начинающиеся с м, буквы, которые находятся в центре словаря. Видно, что untel не может быть в первой половине, поэтому мы ограничиваем поиск второй, которая идет от m до z.
Поэтому мы откладываем первую половину и делаем те же рассуждения о второй и так далее по каждой новой части, мы постепенно сокращаем список, переходя либо в левую, либо в правую часть, чтобы неизбежно добраться до страницы, содержащей искомое слово.

Дихотомический принцип поиска может быть обобщен для любого типа проблем, поскольку объекты поля поиска могут сформировать последовательность и можно провести сравнение порядка в последовательности.

Реализовать алгоритм на компьютере легко благодаря рекурсивности, но и он может реализоваться итеративно.

Рекурсивная версия

Базовый код (скриптол):

array A = []

int binarySearch(int value, int starting, int ending)
  if ending < starting return -1
  int mid = (starting + ending)  / 2	
  if A[mid]
      = value :     return mid
      > value :     ending = mid - 1
      < value :     starting = mid + 1   
  /if	 
return  binarySearch(value, starting, ending)

Таблица A просматривается как глобальная переменная, что значительно ускоряет выполнение сценария, а переменные индекса запуска и ending используются для выбора постепенно уменьшенного фрагмента массива.

Применение к текстовой таблице

Код алгоритма:

int binarySearch(text value, int starting, int ending)
  if ending < starting return -1
  int mid = (starting + ending)  / 2
  int result = strcmp(value, A[mid])  	

  if result
  = 0 :  return mid
  < 0 :  ending = mid - 1
  > 0 :  starting = mid + 1   
  /if
return  binarySearch(value, starting, ending)

Изменилась только функция сравнения. Функция strcmp возвращает 0, когда строки идентичны, число меньше 0, если первая классифицируется до второй, и больше 0, если нет.

Итеративная версия

Базовый код (скриптол):

int binarySearch(int value, array A)
  int starting = 0
  int ending = A.size() 
  int mid
  int length
  
  while forever  
      if starting > ending return -1   
      length = ending - starting 

      if length = 0
          if value = A[starting] return starting
          return -1 
       /if	 
      mid = starting + int(length / 2)

      if value 
          < A[mid] : ending = mid - 1
          > A[mid] : starting = mid + 1
      else
           return mid
      /if
  /while
return -1

Пример использует массив в качестве параметра функции, но его можно также использовать как глобальную переменную, как и рекурсивный алгоритм.