Проверка бинарного и линейного поисков

3 сентября 2023 г.

Поиск — это фундаментальная операция в информатике, которая относится к процессу поиска определенного элемента или значения из набора данных. В этом посте я рассмотрю два популярных алгоритма поиска — линейный поиск и двоичный поиск. Я расскажу про то, как они работают, какая у них временная сложность и когда их использовать.

Линейный поиск

Линейный поиск — это простой алгоритм поиска, который проверяет каждый элемент в коллекции данных один за другим, пока нужный элемент не будет найден. Он также известен как последовательный поиск. Линейный поиск обычно используется при небольших наборах данных, элементы которых не отсортированы.

Временная сложность линейного поиска равна O(n), где n — количество элементов в коллекции. Это означает, что время, необходимое для поиска нужного элемента, увеличивается линейно с размером набора данных.

Напишем линейный поиск:

1def linear_search(alist: list[int], elem: int) -> int | None:
2    for item in alist:
3        if item == elem:
4            return elem
5    return None

Бинарный поиск

Двоичный поиск — более эффективный алгоритм поиска, который используется, когда элементы отсортированы. Алгоритм работает путем многократного деления интервала поиска пополам, пока не будет найден нужный элемент.

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

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

Напишем бинарный поиск:

 1def binary_search(alist: list[int], elem: int) -> int | None:
 2    lo, hi = 0, len(alist) - 1
 3    while lo <= hi:
 4        mid = (lo + hi) // 2
 5        if elem == alist[mid]:
 6            return elem
 7        elif elem < alist[mid]:
 8            hi = mid - 1
 9        else:
10            lo = mid + 1
11    return None

Проверка и сравнение

Теперь я хотел бы проверить насколько временная сложность этих поисков соответствует фактическому приросту времени выполнения, когда я меняю размер отсортированного входного списка со 100 до 100к элементов:

 1import math
 2import timeit
 3
 4# some previous code
 5
 6def compare_searches():
 7    linear_search_time_log = []
 8    binary_search_time_log = []
 9    elem = -42
10    factor = 1000
11    init_size = 100
12    second_size = init_size * factor
13    for n in (init_size, second_size):
14        alist = [x for x in range(n)]
15        linear_search_time_log.append(
16            timeit.timeit(lambda: linear_search(alist, elem), number=10000)
17        )
18        binary_search_time_log.append(
19            timeit.timeit(lambda: binary_search(alist, elem), number=10000)
20        )
21
22    print(
23        "time ratio of linear search",
24        linear_search_time_log[1] / linear_search_time_log[0],
25    )
26    print("complexity ratio of linear ", second_size / init_size)
27    print()
28    print(
29        "time ratio of binary search",
30        binary_search_time_log[1] / binary_search_time_log[0],
31    )
32    print("complexity ratio of binary", math.log2(second_size) / math.log2(init_size))
33
34
35if __name__ == "__main__":
36    compare_searches()

Здесь я замеряю скорость работы поисков со 100 элементами и 100000 элементами, используя модуль timeit, а потом сравниваю отношение затраченного времени с соотношением временной сложности, этот код выдает:

time ratio of linear search 853.5901770657323
complexity ratio of linear  1000.0

time ratio of binary search 2.361164882780545
complexity ratio of binary 2.5

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

 1import math
 2import timeit
 3
 4
 5def linear_search(alist: list[int], elem: int) -> int | None:
 6    for item in alist:
 7        if item == elem:
 8            return elem
 9    return None
10
11
12def binary_search(alist: list[int], elem: int) -> int | None:
13    lo, hi = 0, len(alist) - 1
14    while lo <= hi:
15        mid = (lo + hi) // 2
16        if elem == alist[mid]:
17            return elem
18        elif elem < alist[mid]:
19            hi = mid - 1
20        else:
21            lo = mid + 1
22    return None
23
24
25def compare_searches():
26    linear_search_time_log = []
27    binary_search_time_log = []
28    elem = -42
29    factor = 1000
30    init_size = 100
31    second_size = init_size * factor
32    for n in (init_size, second_size):
33        alist = [x for x in range(n)]
34        linear_search_time_log.append(
35            timeit.timeit(lambda: linear_search(alist, elem), number=10000)
36        )
37        binary_search_time_log.append(
38            timeit.timeit(lambda: binary_search(alist, elem), number=10000)
39        )
40
41    print(
42        "time ratio of linear search",
43        linear_search_time_log[1] / linear_search_time_log[0],
44    )
45    print("complexity ratio of linear ", second_size / init_size)
46    print()
47    print(
48        "time ratio of binary search",
49        binary_search_time_log[1] / binary_search_time_log[0],
50    )
51    print("complexity ratio of binary", math.log2(second_size) / math.log2(init_size))
52
53
54if __name__ == "__main__":
55    compare_searches()

Метки

Если вам понравился пост, можете поделиться им в соцсетях: