Бинарный поиск
Введено
9:10
Algorithms and Programming (Алгоритмы и программирование)
Представьте телефонную книгу с миллионом имен, и вам нужно найти одно. Проверяйте их по очереди, и можно стоять весь день. Есть способ найти его примерно за…
Озвучивание на английском · переключаемые субтитры на английском и китайском языках
In this lesson
| English | Значение |
|---|---|
| sorted/ˈsɔːtɪd/ | отсортированный |
| Binary search/ˈbaɪnəri sɜːtʃ/ | бинарный поиск |
| target/ˈtɑːɡɪt/ | целевой элемент |
| middle/ˈmɪdl/ | середина |
| halves/hɑːvz/ | половина (двух) |
| comparison/kəmˈpærɪsn/ | сравнение |
| linear search/ˈlɪnɪə sɜːtʃ/ | линейный поиск |
Быстрый поиск в отсортированном списке
- Бинарный поиск — быстрый способ найти целевое значение в отсортированном списке.
- «Отсортированный» означает, что значения расположены в порядке — от наименьшего к наибольшему, например.
- Он намного быстрее, чем проверка каждого элемента.
- Но у него есть одно строгое требование.
Бинарный поиск требует отсортированных данных. На неотсортированном списке он может перепрыгнуть через целевое значение и пропустить его. Всегда сортируйте сначала — или используйте другой поиск.
Бинарный поиск можно использовать только на данных, которые:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
На неотсортированных данных он может пропустить целевой элемент.
Проверьте середину, затем сократите вдвое
- Идея проста: проверьте средний элемент. Затем:
- если средний равен целевому, вы нашли его;
- если целевое меньше, ищите только в левой половине;
- если целеемое больше, ищите только в правой половине.

Бинарный поиск сокращает диапазон на каждом шаге (список должен быть отсортирован)
Линейный против бинарного поиска
бинарный поиск сокращает диапазон наполовину на каждом шаге
Линейный поиск проверяет каждый элемент; бинарный поиск делит отсортированный список пополам при каждом сравнении, поэтому требует значительно меньше шагов.
Если целевой элемент больше среднего, бинарный поиск далее смотрит в:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Более крупный целевой элемент должен находиться в правой (большей) половине.
Каждое сравнение в бинарном поиске ______ оставшуюся часть списка.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Деление пополам на каждом шаге — причина высокой скорости.
Примерно сколько проверок бинарного поиска потребуется для отсортированного списка из 1000 элементов? (2^10 = 1024)
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Поскольку 2^10 = 1024 ≥ 1000, достаточно примерно 10 делений пополам.
Почему это так быстро
- Каждое сравнение уменьшает оставшуюся часть списка вдвое.
- Для 1000 элементов линейный поиск может потребовать до 1000 проверок.
- Бинарный поиск требует не более ~10, потому что $2^{10} = 1024$.
- Чем больше список, тем больше преимущество бинарного поиска.
Бинарный поиск находит 14 в [2,5,8,11,14,17,20] за сколько сравнений?
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Середина 11 → вправо; середина 17 → влево; середина 14 → найдено: 3 сравнения.
На большом отсортированном списке линейный поиск требует меньше сравнений, чем бинарный.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Ложь. Бинарный поиск на каждом шаге делит список пополам, поэтому он требует гораздо меньше сравнений, чем последовательная проверка каждого элемента.
Бинарный поиск против линейного
- Линейный поиск проверяет каждый элемент по очереди.
- Бинарный поиск превосходит его на больших отсортированных списках, сокращая область поиска вдвое на каждом шаге.
Найдите 14 в [2, 5, 8, 11, 14, 17, 20]. Средний элемент — 11; 14 > 11 → ищем правую половину [14, 17, 20]. Средний элемент — 17; 14 < 17 → ищем [14]. Средний элемент — 14: найден всего за 3 сравнения. Линейный поиск занял бы 5.
Бинарный поиск находит цель в отсортированном списке, проверяя средний элемент и оставляя только ту половину, которая может её содержать. Каждое сравнение уменьшает диапазон вдвое, поэтому для 1000 элементов нужно около 10 проверок — значительно меньше, чем у линейного поиска, который требует 1000. Он работает только с отсортированными данными.