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

Стандартная библиотека 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 на цикл

Библиотека Python разработчика | Книги по питону

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

Стандартная библиотека 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

👍8❤1

hottg.com/BookPython/3451

3.18K viewsJan 4 at 19:43