От также известен под названиями: двоичный поиск, метод деления пополам, метод дихотомии.
На собеседовании вас скорее всего не будут спрашивать напрямую: “Напишите бинарный поиск”. Но могут спросить задачу, решение которой практически полностью повторяет этот алгоритм, с некоторыми изменениями. Поэтому его нужно знать наизусть и уметь его написать за пару минут без подсказок и гугления.
Какую задачу он решает?
Задан отсортированный массив и искомое значение. Необходимо выяснить, содержит ли массив искомое значение и если содержит, то вернуть его индекс.
Тут ключевой момент это то, что массив отсортирован. Это может служить также подсказкой на собеседовании. Если в условии дан именно отсортированный массив, подумайте, может можно применить метод бинарного поиска. Или же массив можно сначала отсортировать, а потом применить метод бинарного поиска.
Как он работает?
Инициализируем левый и правый индексы — началом и концом массива соответственно.
Находим середину между левым и правым индексами.
Если значение в середине совпадает с искомым, то мы возращаем его индекс. Поиск завершен.
Если значение в середине меньше искомого, то из-за того, что массив отсортирован — искомого значения точно нет слева. Т.к. слева все элементы еще меньше. Поэтому искомое значение если и содержиться в массиве — то справа. Поэтому мы может сократить в два раза область поиска и искать только справа. Для этого мы передвигаем левый индекс в середину и переходим к пункту 2.
Если значение в середине больше искомого. То искать нужно слева (справа все значения еще больше). Поэтому передвигаем правый индекс в середину и переходим к пункту 2.
Алгоритм работает за O(log(n)) из-за того, что мы каждый раз в два раза сокращаем область поиска. Тогда как линейный поиск в массиве работает за O(n) (когда мы последовательно сравниваем все элементы массива, пока не найдем заданный).
На данном примере я показал, как искомое значение мы нашли всего за 2 итерации.
Дан отсортированный массив:
[3, 7, 18, 26, 29, 43]. Требуется проверить, содержится ли в нем значение 29 и если да, то какой индекс у элемента со значением 29?
Ответ: индекс 4.
Реализация на языке Java:
public static int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
//Находим середину
//Для большиго размера массивов лучше использовать
//int mid = left + (right - left) / 2; Для предотвращения переполнения
int mid = (left + right) / 2;
//Значение в середине равно искомому значению
if (array[mid] == target) {
return mid;
}
//Искомое значение меньше, чем элемент в середине.
//Следовательно искомое значение слева.
//Поэтому двигаем правый индекс.
//Иначе, искомое значение справа и двигаем левый индекс.
if (array[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
Реализация на языке Python:
def binarySearch(array, target):
left = 0
right = len(array) - 1
while left <= right:
mid = (left + right) // 2
if target == array[mid]:
return mid
if target < array[mid]:
right = mid - 1
else:
left = mid + 1
return -1
Top comments (0)