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

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

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

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

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

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

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

1 def 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 — количество элементов в коллекции. Это означает, что время, необходимое для поиска нужного элемента, увеличивается логарифмически с размером набора данных.

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

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

 1 def 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к элементов:

 1 import math
 2 import timeit
 3 
 4 # some previous code
 5 
 6 def 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 
35 if __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

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

 1 import math
 2 import timeit
 3 
 4 
 5 def 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 
12 def 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 
25 def 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 
54 if __name__ == "__main__":
55     compare_searches()

Метки

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