Видео: Бинарный поиск - Разбор алгоритма для интервью

Всем привет, меня зовут Александр Вагнер, в этом и в последующих видео я расскажу вам про самые основные алгоритмы - как они устроены и как работают.

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

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

Допустим нам дан отсортированный массив из чисел, и число, которое может как быть в этом массиве, так и не быть. И нам нужно просмотреть этот массив и вернуть индекс числа, если оно присутствует в массиве, либо вернуть None, если числа в массиве нет.

Конечно, эту задачу можно решить с обычным циклом for по всем элементам, и на каждой итерации смотреть - есть ли число в массиве или нет, но представьте, если массив состоит из огромного числа элементов, например из миллиона, а нужное нам число лежит где-то в конце массива. Тогда придется очень долго перебирать все числа, пока не найдем нужное.

Здесь как раз и нужен бинарный поиск. Если очень кратко - то мы на каждой итерации будем смотреть - искомое число больше или меньше текущего элемента массива, и в зависимости от этого убирать то половину чисел, которая меньше либо больше текущего элемента.

Код из видео:

from typing import Optional


def binary_search(sorted_list: list, searched_elem: int) -> Optional[int]:
    left_idx = 0
    right_idx = len(sorted_list) - 1

    while left_idx <= right_idx:
        middle_idx = (left_idx + right_idx) // 2
        middle_elem = sorted_list[middle_idx]

        if middle_elem == searched_elem:
            return middle_idx
        elif middle_elem > searched_elem:
            right_idx = middle_idx - 1
        else:
            left_idx = middle_idx + 1

    return None


assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 6) == 5
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], -1) is None
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 0) is None
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 1) == 0
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 10) == 9
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 50) is None
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 9) == 8
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 2) == 1
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 4) == 3
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 8) == 7
print("All tests have been successfully passed!")

Задача на leetcode.

Материал подготовлен с ❤️ редакцией Кухни IT.