На этом шаге рассмотрим программную реализацию алгоритма бинарного поиска.
Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском.
Посмотрим, как написать реализацию бинарного поиска на C++. В следующем примере кода используется массив (серия однотипных элементов, сохраненных в непрерывной последовательности ячеек). Нумерация ячеек начинается с нуля: первая ячейка находится в позиции с номером 0, вторая - в позиции с номером 1 и т. д.
Функция bin_search получает отсортированный массив, загаданное число и количество элементов в массиве. Если значение присутствует в массиве, то функция возвращает его позицию, иначе функция вернет значение -1. Пример работы функции представлен на рис. 1.
Рис.1. Пример работы функции bin_search
При этом мы должны следить за тем, в какой части массива проводится поиск. Вначале это весь массив:
Каждый раз алгоритм проверяет средний элемент:
Код функции bin_search выглядит так:
int bin_search(int mas[], int n, int p) { /* В переменных low и high хранятся границы той части списка, в которой выполняется поиск */ int low = 0, high = p - 1; /* Пока эта часть не сократиться до одного элемента.... */ while(low <= high) { /* вычисляем позицию среднего элемента */ int mid = (low + high) / 2; /* Значение найдено */ if(mas[mid] == n) return mid; /* Значение больше загаданного */ if(mas[mid] > n) high = mid - 1; /* Значение меньше загаданного */ else low = mid + 1; } /* Такого значения нет */ return -1; }
На следующем шаге рассмотрим применение алгоритма бинарного поиска при решении конкретных задач.
