Алгоритмы. Бинарный поиск
Описание алгоритма бинарного поиска
На технических собеседованиях часто встречаются задачи, которые требуют применения алгоритма бинарного поиска. Наиболее классической задачей для его применения является поиск элементов в упорядоченном массиве. Рассморим реализацию решения данной задачи:
1def search(arr, target):
2 start, end = 0, len(arr)
3 while start < end:
4 mid = (start + end) // 2
5 if arr[mid] == target:
6 return True
7 elif arr[mid] < target:
8 start = mid + 1
9 else:
10 end = mid
11 return FalseПри решении задачи простым перебором всех элементов массива - сложность была бы O(n), но в случае с бинарным поиском сложность будет O(log N). Это означает, что в общем и худшем случае интервал поиска на каждом шаге алгоритма будет сокращаться в два раза.
Типичной ошибкой при применении этого алгоритма является ошибка в индексах. Используйте полуинтервалы (start = 0, end = len(arr)), а не интервалы (когда правая граница включена). Сформулируйте для себя инвариант. Для задачи выше он будет звучать как “arr[start] не превосходит искомый элемент, arr[end], наоборот, превосходит”. Тогда при чтении кода вы можете проверить этот инвариант.
Как правило, бинарный поиск применяется на монотонных данных. Функция называется монотонно возрастающей, если каждое её значение строго больше предыдущего. Функция называется монотонно неубывающей, если каждое её значение не меньше предыдущего. Аналогично функция может быть монотонно убывающей (каждое значение строго меньше предыдущего) или монотонно невозрастающей (каждое значение не больше предыдущего). Если функция обладает хотя бы одним из этих свойств, то она монотонная.
Другими примерами задач, где может примененятся могут являться следующие:
1. Дано положительное целое число х. Необходимо вычислить квадратный корень для этого числа. Ответ округлить вниз до ближайшего целого числа. Запрещено использовать стандартные функции и методы языка.
2. Дан отсортированный массив целых чисел и целевое значение. Вернуть индекс целевого числа, если он существует в массиве. Если его там нет, то вернуть индекс позиции, где он мог бы быть.
Для всех задач прослеживается наличие монотонных данных имеющих начало и окончание, что позволяет применять данный алгоритм.
