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

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

Постановка задачи поиска

В практической деятельности приходится решать такие прикладные задачи, в которых необходимо локально или автономно произвести поиск нужных объектов. Рассмотрим задачу поиска элемента в массиве.

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

Задача поиска в этом случае состоит в отыскании индекса (индексов) элемента по заданному свойству элемента.

Существуют два возможных результата поиска:

· поиск оказался удачным, т.е. позволил определить положение элемента в массиве;

· поиск оказался неудачным, т.е. достигнут конец массива, но элемент с заданным свойством отсутствует.

Простейшим методом поиска является последовательный просмотр таблицы, одномерного массива или строки до нахождения элемента с требуемыми свойствами или установления факта, что такого элемента нет. Для массива, данные в котором не упорядочены сортировкой, единственный путь поиска заданного элемента состоит в сравнении каждого элемента массива с заданным. При совпадении некоторого элемента массива с заданным, его позиция в массиве фиксируется. Этот алгоритм называется последовательным,или линейным,поиском. Ядром такого алгоритма является цикл по индексу массива. Так, если в массиве int a[n]нужно найти введенное с клавиатуры целое число х, о котором никакой дополнительной информации нет, то соответствующий цикл можно записать следующим образом:

for (i = 0; i < n; i++) if (a[i] == x) k = i;

Этот способ решения обладает двумя существенными недостатками:

· если значение х встречается в массиве несколько раз, то будет найдено последнее из них;

· после того, как нужное значение уже найдено, массив просматривается до конца, то есть всегда выполняется п сравнений.

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

while ((i < n) && (a[i] != x)) i++;

Наиболее эффективным и распространенным методом непоследовательного поиска в одномерных упорядоченных массивах является бинарныйпоиск, который называют также методом половинного деления, методом дихотомии, методом логарифмического поиска или методом деления пополам. Основная идея бинарного поиска состоит в том, что сначала искомый элемент х сравнивается со средним элементом массива а[n]. Результат сравнения либо приводит к решению задачи, либо позволяет определить, в какой части массива - левой или правой - продолжать поиск. После каждой такой итерации область поиска сокращается вдвое и не более чем через [log₂n] сравнений мы закончим поиск, то есть либо попадем на элемент х, либо покажем, что х не принадлежит массиву а[n]. Например, при n = 1000 бинарный поиск в 100 раз быстрее последовательного, а при n = 1000000 – в 50000 раз. Разумеется, если массив неупорядоченный, то применить к нему бинарный поиск нельзя. Таким образом, факт упорядоченности элементов в массиве играет ключевую роль при бинарном поиске.