Бинарный поиск… обман или гениальность? Допустим, у вас есть отсортированная *уведомление, что я сказал отсортированная*пачка из 100 бумаг, и вам нужно найти страницу номер 72. С чего бы вы начали? С самого начала? Конечно, нет! Это не эффективно. Здесь на помощь приходит бинарный поиск.

Традиционно при поиске в массиве простым подходом является линейный поиск. Это просто просмотр длины массива, пока вы не найдете искомый элемент. Если у вас большой массив, это может быстро стать проблематичным.

К счастью, здесь на помощь приходит бинарный поиск. Суть в том, что он должен быть отсортированным массивом. Алгоритм бинарного поиска позволяет искать в отсортированном массиве путем многократного деления интервала поиска пополам.

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

Двигаясь дальше, это означает, что мы знаем, что искомый элемент должен находиться во второй половине массива. Начиная с середины, мы знаем, что 23 меньше 56. Необходимо сохранить только первую половину этого интервала поиска.

Теперь осталось только два элемента массива. Повторите процесс, и мы получим наш параметр поиска. С помощью этого метода мы сокращаем размер нашего массива вдвое каждый раз, когда начинаем новый интервал поиска.

вот реализация бинарного поиска в ruby. Как видите, цикл while проходит через массив, устанавливая i равным половине длины массива, чтобы начать с середины. Первый if позаботится о том, чтобы элемент поиска был средним индексом. если это не так и индекс массива больше, чем искомый элемент, он отбрасывает всю вторую половину, так как все числа будут больше, чем искомый элемент. В противном случае это означает, что индекс должен быть меньше элемента поиска, а может быть и наоборот. Вот почему крайне важно, чтобы массив был отсортирован. Если элемент так и не найден, мы просто возвращаем, что его нет в массиве.

Недостатки?

  • Эффективность снижается для небольших наборов данных
  • Будет работать только для наборов данных, которые отсортированы и хранятся в отсортированном виде.
  • Хотя это редкость, существуют типы данных, которые невозможно отсортировать.