Бинарный поиск
| English | Русский |
|---|---|
| sorted/ˈsɔːtɪd/ | отсортированы |
| Binary search/ˈbaɪnəri sɜːtʃ/ | Бинарный поиск |
| target/ˈtɑːɡɪt/ | целевой |
| middle/ˈmɪdl/ | среднее |
| comparison/kəmˈpærɪsn/ | сравнение |
| halves/hɑːvz/ | уменьшается вдвое |
| linear search/ˈlɪnɪə sɜːtʃ/ | линейный поиск |
Быстрый поиск в отсортированном списке
- Бинарный поиск — быстрый способ найти целевое значение в отсортированном списке.
- «Отсортированный» означает, что значения расположены в порядке — от наименьшего к наибольшему, например.
- Он намного быстрее, чем проверка каждого элемента.
- Но у него есть одно строгое требование.
Бинарный поиск требует отсортированных данных. На неотсортированном списке он может перепрыгнуть через целевое значение и пропустить его. Всегда сортируйте сначала — или используйте другой поиск.
Бинарный поиск можно использовать только на данных, которые:
На неотсортированных данных он может пропустить целевой элемент.
Проверьте середину, затем сократите вдвое
- Идея проста: проверьте средний элемент. Затем:
- если средний равен целевому, вы нашли его;
- если целевое меньше, ищите только в левой половине;
- если целеемое больше, ищите только в правой половине.
Линейный против бинарного поиска
бинарный поиск减半范围每一步
Линейный поиск проверяет каждый элемент; бинарный поиск делит отсортированный список пополам при каждом сравнении, поэтому требует значительно меньше шагов.
Если целевой элемент больше среднего, бинарный поиск далее смотрит в:
Более крупный целевой элемент должен находиться в правой (большей) половине.
Каждое сравнение в бинарном поиске ______ оставшуюся часть списка.
Деление пополам на каждом шаге — причина высокой скорости.
Примерно сколько проверок бинарного поиска потребуется для отсортированного списка из 1000 элементов? (2^10 = 1024)
Поскольку 2^10 = 1024 ≥ 1000, достаточно примерно 10 делений пополам.
Почему это так быстро
- Каждое сравнение уменьшает оставшуюся часть списка вдвое.
- Для 1000 элементов линейный поиск может потребовать до 1000 проверок.
- Бинарный поиск требует не более ~10, потому что $2^{10} = 1024$.
- Чем больше список, тем больше преимущество бинарного поиска.
Бинарный поиск находит 14 в [2,5,8,11,14,17,20] за сколько сравнений?
Середина 11 → вправо; середина 17 → влево; середина 14 → найдено: 3 сравнения.
На большом отсортированном списке бинарному поиску требуется гораздо меньше сравнений, чем линейному.
Деление пополам побеждает проверку каждого элемента по отдельности.
Бинарный поиск против линейного
- Линейный поиск проверяет каждый элемент по очереди.
- Бинарный поиск превосходит его на больших отсортированных списках, сокращая область поиска вдвое на каждом шаге.
Поиск [2, 5, 8, 11, 14, 17, 20] элемента 14. Середина — ⟨11⟩; ⟨14⟩ > ⟨11⟩ → ищем правую половину [14, 17, 20]. Середина — ⟨17⟩; ⟨14⟩ < ⟨17⟩ → ищем [14]. Середина — ⟨14⟩ — найдено всего за 3 сравнений. Линейный поиск занял бы 5.
Бинарный поиск находит цель в отсортированном списке, проверяя средний элемент и оставляя только ту половину, которая может её содержать. Каждое сравнение уменьшает диапазон вдвое, поэтому для 1000 элементов нужно около 10 проверок — значительно меньше, чем у линейного поиска, который требует 1000. Он работает только с отсортированными данными.