Бинарный поиск

Последовательный или линейный поиск

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

Для последовательного поиска в среднем требуется (N+1)/2 сравнений. Таким образом, порядок алгоритма - линейный - O(N).

Программная иллюстрация линейного поиска в неупорядоченном массиве приведена в следующем примере, где mas - исходный массив, key - ключ, который ищется; функция возвращает индекс найденного элемента или EMPTY - если элемент отсутствует в массиве.

{===== Программный пример 6.1 =====}

int LinSearch(int* mas, int key)

{

for(int i=0; i<N; i++) // перебор элементов массива

if(mas[i] == key) return i; // ключ найден,

// возврат индекса

return EMPTY; // просмотр завершен, но ключ не найден

}

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

В рассматриваемом методе поиск отдельной записи с определенным значением ключа напоминает поиск фамилии в телефонном справочнике. Сначала приближенно определяется запись в середине таблицы и анализируется значение ее ключа. Если оно слишком велико, то анализируется значение ключа, соответствующего записи в середине первой половины таблицы, и указанная процедура повторяется в этой половине до тех пор, пока не будет найдена требуемая запись.

Если значение ключа слишком мало, испытывается ключ, соответствующий записи в середине второй половины таблицы, и процедура повторяется в этой половине. Этот процесс продолжается до тех пор, пока не будет найден требуемый ключ или не станет пустым интервал, в котором осуществляется поиск.

Для того чтобы найти нужную запись в таблице, в худшем случае требуется log₂(N) сравнений. Это значительно лучше, чем при последовательном поиске.

Программная иллюстрация бинарного поиска в упорядоченном массиве приведена в следующем примере, где mas - исходный массив, key - ключ, который ищется; функция возвращает индекс найденного элемента или EMPTY - если элемент отсутствует в массиве.

{===== Программный пример 6.2 =====}

int BinSearch(int* mas, int key)

{

int first = 0, last = N-1; // начальные границы интервала

int i;

while(first <= last){ // пока интервал поиска не равен 0

i = (first + last) / 2; // середина интервала

if(mas[i] == key) return i; // ключ найден, возврат

else {

if(mas[i] < key)

first = i + 1;//поиск в правом подинтервале

else last = i - 1; // поиск в левом подинтервале

}

}

return EMPTY; // ключ не найден

}

Трассировка бинарного поиска ключа 275 в исходной последовательности:

75, 151, 203, 275, 318, 489, 524, 519, 647, 777

представлена в табл. 6.1.

Таблица 6.1

Итерация	first	last	i	K[i]

Алгоритм бинарного поиска можно представить и несколько иначе, используя рекурсивное описание. В этом случае граничные индексы интервала first и last являются параметрами алгоритма.

Рекурсивная процедура бинарного поиска представлена в программном примере 3.6. Для выполнения поиска необходимо при вызове процедуры задать значения ее формальных параметров first и last - 1 и N соответственно, где first, last - граничные индексы области поиска.

{===== Программный пример 6.3 =====}

int BinSearch(int* mas, int key, int first, int last)

{

if(first > last) return EMPTY; // ключ не найден

int i = (first + last) / 2; // середина интервала

if(mas[i] == key) return i; // ключ найден, возврат

else

{

if(mas[i] < key)

return BinSearch(mas, key,

i + 1, last); // поиск в правом подинтервале

else return BinSearch(mas, key,

first, i - 1);// поиск в левом подинтервале

}

}

Известно несколько модификаций алгоритма бинарного поиска, выполняемых на деревьях, которые будут рассмотрены в лекции 13.

Дата добавления: 2014-01-07