Лабораторная работа №2: "Угадай число"

Цель работы

Реализация алгоритма бинарного поиска и оценка его эффективности при работе с упорядоченными числовыми последовательностями.

Задание

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

Реализация

def guess_number_bin(start, end, target) -> (int|None, int):
    numbers = [i for i in range(start, end + 1)]
    attempts = 0
    l = 0
    r = len(numbers) - 1

    while l <= r:
        attempts += 1
        middle_ind = (l + r) // 2
        middle = numbers[middle_ind]

        if middle == target:
            return middle_ind, attempts
        elif middle < target:
            l = middle_ind + 1
        else:
            r = middle_ind - 1
    return None, attempts

Вывод

Был реализован алгоритм бинарного поиска, который продемонстрировал высокую скорость работы на больших данных. Тестирование показало, что для диапазона в миллион значений программе требуется не более 20 итераций. Это подтверждает теоретическую эффективность алгоритма со сложностью $O(\log n)$, что значительно превосходит линейный поиск.