01 binary search.py

# Бинарный поиск. [O(log n)]
# Создаем функцию "binary_search", которая принимает два входных параметра:
# список "search_list" и число для поиска "number".
# Эта функция возвращает индекс элемента, который является числом для поиска "number".

def binary_search(search_list, number):
    # В переменных "low" и "high" хранятся границы области поиска в списке "search_list".
    # Функция "len()" возвращает количество элементов в списке.
    low = 0
    high = len(search_list) - 1
    # Создаем цикл while, который работает пока нижняя граница области поиска меньше или равна
    # верхней границе этой области поиска.
    # После выполнения одного из условий, область поиска уменьшается и цикл while продолжает свою работу сначала.
    while low <= high:
        # Находим средний элемент списка "search_list". Переменная "mid" - индекс этого среднего элемента.
        # Переменная "guess" - значение по этому индексу. Значение переменной "mid" округляется в меньшую сторону.
        mid = (low + high) // 2
        guess = search_list[mid]
        # Если значение среднего элемента списка "search_list" равно числу, которое мы ищем,
        # то функция "binary_search" возвращает индекс этого среднего элемента.
        # Ключевое слово "return" выходит из функции и возвращает какое-либо значение.
        if guess == number:
            return mid
        # Если значение среднего элемента списка "search_list" больше числа, которого мы ищем,
        # то верхняя граница области поиска становится равной на одну позицию меньше,
        # чем индекс этого среднего элемента.
        if guess > number:
            high = mid - 1
        # Иначе если значение среднего элемента списка "search_list" меньше числа, которого мы ищем,
        # то нижняя граница области поиска становится равной на одну позицию больше,
        # чем индекс этого среднего элемента.
        else:
            low = mid + 1
    # Если число для поиска отсутствует в списке "search_list" (условие "low <= high" не является верным,
    # этот факт означает, что область поиска пуста), то функция "binary_search" возвращает "None".
    # "None" означает nil (ничто) в Python. Мы используем это, чтобы определять, что числа нет в списке.
    return None


# Создаем список чисел "my_list".
my_list = [1, 3, 5, 7, 9]
# Пытаемся найти индекс элемента, который находится в списке "my_list".
# Функция "print()" выводит некую указанную информацию на экран или на какое-либо другое устройство вывода.
print(binary_search(my_list, 7))
# Пытаемся найти индекс элемента, который не находится в списке "my_list".
print(binary_search(my_list, 8))