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