Бинарный поиск (метод деления пополам)
Будем предполагать, что имеем упорядоченный по возрастанию массив чисел. Основная идея - выбрать случайно некоторый элемент AM и сравнить его с аргументом поиска Х. Если AM=Х, то поиск закончен; если AM <X, то мы заключаем, что все элементы с индексами, меньшими или равными М, можно исключить из дальнейшего поиска. Аналогично, если AM >X.
Выбор М совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача- исключить как можно больше элементов из дальнейшего поиска. Оптимальным решением будет выбор среднего элемента, т.е. середины массива.
Рассмотрим пример, представленный на рис. 5.7. Допустим нам необходимо найти элемент с ключом 52. Первым сравниваемым элементом будет 49. Так как 49<52, то ищем следующую середину среди элементов, расположенных выше 49. Это число 86. 86>52, поэтому теперь ищем 52 среди элементов, расположенных ниже 86, но выше 49. На следующем шаге обнаруживаем, что очередное значение середины равно 52. Мы нашли элемент в массиве с заданным ключом.
Программы на псевдокоде и Паскале:
| Low = 1
hi = n while (low <= hi) do mid = (low + hi) div 2 if key = k(mid) then search = mid return endif if key < k(mid) then hi = mid - 1 else low = mid + 1 endif endwhile search = 0 return | low := 1;
hi := n; while (low <= hi) do begin mid := (low + hi) div 2; if key = k[mid] then begin search := mid; exit; end; if key < k[mid] then hi := mid - 1 else low := mid + 1; end; search := 0; exit |
При key = 101 запись будет найдена за три сравнения (в последовательном поиске понадобилось бы семь сравнений).
Если С - количество сравнений, а n - число элементов в таблице, то
С = log2n.
Например, n = 1024.
При последовательном поиске С = 512, а при бинарном
С = 10.
Можно совместить бинарный и индексно-последовательный поиск (при больших объемах данных), учитывая, что последний также используется при отсортированном массиве.
