Двоичный поиск

Двоичный поиск §

📂 Алгоритмы

Время: O(log n)

Двоичный (бинарный) поиск работает, только если исходный список отсортирован.

def binary_search(array: list, item: int) -> int | None:
    """
    Find `item` in `array` sorted in ascending order.
 
    :param array: list of integers sorted in ascending order.
    :param item: integer which index in array we want to find.
    :return: index of `item` in `array`, or None if not found.
    """
    # Limits of the array where we search:
    low = 0
    high = len(array) - 1
 
    while low <= high:
        mid_index = int((low + high) / 2)
        guess = array[mid_index]
 
        if guess == item:
            return mid_index
 
        if guess > item:
            high = mid_index - 1
        else:
            low = mid_index + 1
 
    return None
 
 
my_list = [i for i in range(0, 1024)]
 
print(binary_search(array=my_list, item=999))

Ссылки §

• ==Managing Ordered Sequences with Bisect==
• https://www.techinterviewhandbook.org/algorithms/sorting-searching/

---

📂 Алгоритмы | Последнее изменение: 07.02.2024 20:18