Сравнения
Ещё возможны
Линейному поиску нужно

  • Искомое
  • Ещё возможны
  • Сравниваются
  • Исключено
  • Найдено

Подробнее о двоичном поиске

Двоичный поиск

Двоичный (бинарный) поиск находит значение в отсортированном списке, всякий раз заглядывая в середину. Если среднее значение слишком мало, искомое может быть только после него; если слишком велико — только перед ним. В любом случае отсекается половина оставшегося. Выберите искомое значение, пройдите поиск по шагам и смотрите, как затенённая часть сжимается, пока значение не найдётся или ничего не останется. Нажмите «Пуск», чтобы посмотреть поиск, или «Шаг» и «Назад», чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Пунктирная линия отмечает искомое значение, а затенённая часть — где оно ещё может быть. Двоичному поиску нужен отсортированный список, поэтому неотсортированный список сначала сортируется. Выберите значение, число столбиков или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.

Как это работает

  1. Выберите искомое значение и число столбиков. Или введите свои числа: двоичный поиск сначала их отсортирует.
  2. Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место поиска.
  3. Сравните плитку «Сравнения» с плиткой «Линейному поиску нужно» для значения ближе к концу или отсутствующего в списке.

Как работает двоичный поиск

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

Почему он такой быстрый

Каждое сравнение вдвое сокращает оставшуюся часть. Если в начале n значений, то после k сравнений остаётся не больше примерно n/2ᵏ, поэтому поиск заканчивается не более чем через ⌊log₂ n⌋ + 1 сравнений: 6 для 40 значений, 10 для 1000, 20 для миллиона. Линейному поиску может понадобиться просмотреть каждое значение. Подвох в том, что список должен быть отсортирован, а поддерживать его отсортированным или сначала сортировать — тоже затраты.

Часто задаваемые вопросы

Как работает двоичный поиск?

Он сравнивает искомое значение со средним значением той части отсортированного списка, где оно ещё может быть. Равенство означает, что значение найдено; иначе половина, где его быть не может, отбрасывается, и поиск продолжается в другой половине, пока значение не найдётся или ничего не останется.

Сколько сравнений нужно двоичному поиску?

Не больше ⌊log₂ n⌋ + 1 для списка из n значений: 6 для 40, 10 для 1000, 20 для миллиона. Каждое сравнение вдвое сокращает остаток.

Почему двоичному поиску нужен отсортированный список?

Потому что только в отсортированном списке одно сравнение говорит, с какой стороны искомое значение. В неотсортированном списке меньшее значение в середине ничего не говорит о том, где искомое, поэтому ничего нельзя отсечь.

Какое значение он находит, если есть повторы?

Любое из них, в зависимости от того, куда попадают середины. Варианты, которые после совпадения продолжают искать влево или вправо, находят первое или последнее вхождение.

Отправляются ли куда-нибудь мои числа?

Нет. Поиск работает в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор