Двійковий пошук

Коротко: Двійковий пошук знаходить елемент у відсортованому списку, багаторазово ділячи діапазон пошуку навпіл, — замість того щоб перевіряти всі елементи по одному.

Докладніше: Він порівнює шукане значення із середнім елементом: якщо воно менше, продовжує ліворуч, якщо більше — праворуч. Тому для n елементів потрібно лише близько log₂(n) кроків — для мільйона елементів щонайбільше 20 (час O(log n), див. О-нотація). Умова — відсортований набір даних із доступом за індексом.

Подробиці

def binary_search(items, target):

Див. також: алгоритми, сортування, О-нотація, індекс масиву