Що означає binary search?

Де і як уживається

Часова складність — O(log n), тому для мільйона елементів потрібно лише близько 20 кроків. Метод працює лише з відсортованими даними. На тій самій ідеї ґрунтується git bisect, який знаходить коміт, що додав помилку.

Приклади речень

1. Since the timestamps are already sorted, we can use binary search instead of scanning the whole list.

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

   Відомий порядок даних дозволяє щоразу відкидати половину списку й не перевіряти всі елементи.

2. I did a binary search through the commits and found the one that broke the build.

   Я виконав бінарний пошук серед комітів і знайшов той, що зламав збірку.

   Послідовне звуження набору комітів допомогло визначити зміну, після якої виник збій.

Поширені словосполучення

• implement binary search
• binary search tree
• O(log n)
• git bisect