Двоичный поиск

Двоичный (или бинарный) поиск основан на итерационном сравнении ключа поиска со средним элементом массива.

При каждой итерации интервал анализа делится пополам (на 2): 1/2, 1/4, 1/8 и т.д., откуда этот метод поиска и получил свое название (ещё один вариант названия – дихотомический). В зависимости от результата сравнения, выбирается нижний или верхний интервал. Процесс продолжается до тех пор, пока не будет найдено совпадение или длина интервала анализа не станет равной единице, и если при этом нет совпадения, то фиксируется неудача поиска.

Этот метод поиска значительно эффективнее чем последовательный поиск, но требует, чтобы данные были предварительно упорядочены (отсортированы).

В худшем случае выполняется не более

log₂(N) + E

сравнений (где E < 0.0861), в связи с чем двоичный поиск ещё называется "логарифмическим поиском".

Аналогичная процедура на языке Си++:
int search_b(float* item, int n, float key)
{
int low, high, mid;
low = 0;
high= n - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (key < item[mid])
high = mid - 1;
else
if (key > item[mid])
low = mid + 1;
else
return mid;
}
return -1;
}

Существуют модификации алгоритма:

· с двумя переменными вместо low, high, mid (нижней, верхней границы и середины интервыла анализа) - текущее положение и величина его изменения. Такой метод требует аккуратности;

· алгоритм со вспомогательными таблицами.

Поиск с использованием чисел Фибоначчи

F(n) = F(n−1) + F(n−2), F(0) = 0, F(1) = 1, F(2) = 1,...

F = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,... Числа Фибоначчи используются вместо степеней двойки при делении интервала. В данном случае вместо деления используются только сложение и вычитание. Для этого требуется таблица чисел Фибоначчи, или процедура их вычисления, исходя из длины интервала. Данный метод проще реализуется при размере массива, на 1 меньше очередного числа Фибоначчи N + 1 = F_k.