Поиск в массивах. Бинарный поиск.

При решении многих задач возникает необходимость определить, содержит ли массив определенную информацию или нет. Например, проверить, есть ли в списке студентов фамилия Петров. Задачи такого типа называются поиском в массиве.

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

В случае если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых — метод бинарного поиска (двоичный поиск, логарифмический поиск, метод деления пополам, дихотомия).

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

Метод (алгоритм) бинарного поиска реализуется следующим образом:

1. Сначала образец сравнивается со средним (по номеру) элементом массива.

· Если образец равен среднему элементу, то задача решена.

· Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое значение verh принимается sred+1, а значение niz не меняется.

· Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется.

2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (niz-verh) /2+verh вычисляется новое значение sred и поиск продолжается.

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

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