Если вам нужно выполнить поиск в отсортированной коллекции, то…
Загружаем изображение…
Если вам нужно выполнить поиск в отсортированной коллекции, то бинарный поиск — это именно то, что вам нужно. Этот простой алгоритм сравнивает искомое значение с элементом в середине массива; результат определяет, какую половину нужно искать дальше.
Стандартная библиотека Python предоставляет возможность использовать бинарный поиск без его непосредственной реализации. Функция bisect_left возвращает самую левую позицию элемента в отсортированном списке, а bisect_right — самую правую.
from random import randrange
from bisect import bisect_left
n = 1000000
look_for = 555555
lst = sorted(randrange(0, n) for _ in range(n))
%timeit look_for in lst
# 69.7 ms ± 449 µs на цикл
%timeit look_for == lst[bisect_left(lst, look_for)]
# 927 ns ± 2.28 ns на цикл
Результаты демонстрируют, что использование бинарного поиска через bisect_left быстрее, чем стандартный поиск в списке с помощью оператора in.
👉@BookPython
Стандартная библиотека Python предоставляет возможность использовать бинарный поиск без его непосредственной реализации. Функция bisect_left возвращает самую левую позицию элемента в отсортированном списке, а bisect_right — самую правую.
from random import randrange
from bisect import bisect_left
n = 1000000
look_for = 555555
lst = sorted(randrange(0, n) for _ in range(n))
%timeit look_for in lst
# 69.7 ms ± 449 µs на цикл
%timeit look_for == lst[bisect_left(lst, look_for)]
# 927 ns ± 2.28 ns на цикл
Результаты демонстрируют, что использование бинарного поиска через bisect_left быстрее, чем стандартный поиск в списке с помощью оператора in.
👉@BookPython