Бинарный поиск в JavaScript. Практический пример

https://codeburst.io/binary-search-in-javascript-a-practical-example-7fda60ce59a1
  • Перевод
  • Tutorial
image

Что такое бинарный поиск?


Когда нужно выполнить поиск в массиве, простейшим способом может быть использование indexOf() или, возможно, цикла for(). Любой из этих способов будет начинать перебирать массив начиная с начала и переходить по каждому элементу массива до тех пор, пока не будет найдено нужное значение.

Теперь сравним это с бинарным поиском.

Бинарный поиск позволяет выполнять поиск в отсортированном массиве путем многократного разбиения массива пополам.

Бинарный поиск выполняется путем проверки того, является ли искомое значение больше, меньше или равно среднему значению в нашем массиве:

  • Если оно меньше, мы можем удалить правую половину массива.
  • Если оно больше, мы можем удалить левую половину массива.
  • Если оно равно, мы возвращаем значение

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

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

Проект


Недавно я опубликовал статью о том, как я написал интерактивный 30-дневный график цены bitcoin с API на React.

Одним из наиболее важных аспектов диаграммы является подсказка, отображающая соответствующие данные при наведении курсора на диаграмму. При перемещении мыши на подсказке обновляются данные из ближайшей точки диаграммы. Пример:

image

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

У нас есть массив всех координат и соответствующих им данных. Координаты находятся внутри объекта, и каждый объект имеет svgX ключ. Выглядит это примерно так:

svgData = [
  {svgX: 1367.844, data...},
  {svgX: 1684.478, data...},
  {svgX: 1168.474, data...},
  {svgX: 1344.854, data...},
  // etc.
]


Изначально я использовал простой цикл for, чтобы сравнить текущую координату X курсора мыши со всеми значениями svgX в моем массиве данных.

Цикл


Вот как выглядит код цикла for. Мы перебираем все значения svgX, и объект со значением, которое ближе к координате X курсора мыши — это тот объект, данные которого мы хотим показать.

const {svgWidth} = this.props;
let closestPoint = {};
 for(let i = 0, c = svgWidth; i < svgData.length; i++){
   if ( Math.abs(svgData[i].svgX — this.state.hoverLoc) <= c ){
     c = Math.abs(svgData[i].svgX — this.state.hoverLoc);
     closestPoint = svgData[i];
   }
 }

Сначала мы получаем ширину нашего svg элемента и создаем пустой объект для хранения нашей ближайшей точки.

const {svgWidth} = this.props;
let closestPoint = {};

Затем мы перебираем массив данных. Каждое svgX значение объекта в нашем массиве сравнивается с координатой X курсора мыши. Если текущая итерация цикла имеет значение ближе к курсору, чем любая другая итерация, то эта точка устанавливается как наша ближайшая точка.

При небольшом количестве данных этот метод является относительно быстрым. Однако, если у нас есть большой объем данных, этот вариант уже не будет таким эффективным.

Бинарный поиск


Ниже приведен пример кода бинарного поиска для поиска ближайшего значения:


const binarySearch = (data, target, start, end) => {
  if(end < 1) return data[0];
  const middle = Math.floor((start + (end - start)/2);
  if (target == data[middle].svgX) return data[middle];
  if (end — 1 === start) return Math.abs(data[start].svgX — target) > Math.abs(data[end].svgX — target) ? data[end] : data[start]; 
  if (target > data[middle].svgX) return binarySearch(data,target,middle,end);
  if (target < data[middle].svgX) return binarySearch(data,target,start,middle);
}
let closestPoint = binarySearch(data,target, 0, data.length-1)

Нам нужно пять основных составляющих для нашего бинарного поиска:

  1. data — данные. Массив объектов.
  2. target — цель. Расположение курсора мыши (координата x).
  3. start — начало. Начальная позиция в массиве для текущей итерации бинарного поиска.
  4. еnd — конец. Конечная позиция в массиве для текущей итерации бинарного поиска.
  5. мiddle — середина. Середина массива для текущей итерации бинарного поиска.

Я знаю, что это немного запутанно, поэтому давайте рассмотрим пример, который упрощает приведенный выше код. В этом примере нашим целевым значением будет 3,7. Мы будем искать в массиве из пяти увеличивающихся чисел от 1 до 5.

Как видно из приведенного выше кода в строке 10, при запуске бинарного поиска мы передаем на вход весь массив данных, объект мыши, начальную позицию 0 и конечную позицию, равную полному размеру массива:
Поиск в полном массиве
Когда у нас есть наши данные, середину массива найдем путем деления на два, суммы из начальной и конечной позиций. Чтобы не получить дробь, результирующее число округляется вниз:

const middle = Math.floor((start + (end - start)/2);

Таким образом, середина 0 + (4-0)/2 округленная вниз = 2:
Поиск среднего = data[2]
Мы помним, что для этого примера наше целевое значение равно 3,7. После того как мы нашли среднюю позицию, мы проверяем, равна ли она нашему целевому значению. Если это так, мы возвращаем объект, и все готово!

if (target == data[middle].svgX) return data[middle];

К сожалению, среднее значение массива = 3. А нашей целью является 3,7.

Далее мы проверим, совпадает ли наша конечная позиция — 1, с нашей начальной позицией:

if (end — 1 === start) {
  return Math.abs(data[start].svgX — target) > Math.abs(data[end].svgX — target) ? data[end] : data[start];
}

Это условие сработает, когда наш массив уменьшился до двух финальных значений, и наша цель находится между ними. В этом случае мы возвращаем ближнее значение.

На текущей итерации условие вернет false.

Далее мы проверяем, больше ли наше целевое значение за среднее:

if (target > data[middle].svgX) return binarySearch(data,target,middle,end);

Это наш случай! Целевое значение 3,7 больше чем среднее 3. Мы можем избавиться от первых двух значений в нашем массиве:

image
Используя рекурсию мы возвращаем новый вызов функции binarySearch(). Передаем в функцию наш массив, целевое значение 3,7, среднее значение в качестве начальной позиции и конечное значение в качестве конечной позиции.

Наш новый вызов binarySearch(), будет искать от позиции 2 до data.length-1:

image
Функция находит новую среднюю позицию data[3]:
image
Поскольку наше целевое значение 3,7 меньше среднего значения 4, мы отбрасываем правую сторону массива и возвращаем новый вызов функции binarySearch(). На этот раз наша начальная позиция остается data[2], а конечная позиция меняется на среднюю data[3].
image
Мы дошли до момента, когда наше условие выполнится:

if (end — 1 === start) {
  return Math.abs(data[start].svgX — target) > Math.abs(data[end].svgX — target) ? data[end] : data[start];
}

Поскольку наше конечное значение минус единица равняется нашему начальному значению, мы знаем, что целевое значение находится где-то между ними. Мы должны возвратить элемент массива, значение которого ближе к значению 3,7. Поскольку 4 (конечное значение) ближе, то соответственно мы и возвращаем соответствующий элемент: data[3].

Тест скорости


Если объем данных небольшой, рекурсия может быть медленнее, чем цикл for. При тестировании на jsperf с 10 элементами, рекурсивная функция в среднем на 3% медленнее, чем цикл for. Однако при количестве элементов в 10 000, цикл for на 72% медленнее, чем рекурсивная функция. Это означает, что рекурсия практически в два раза быстрее, чем цикл for, и это огромная экономия времени!

Надеюсь, теперь вам понятны основы бинарного поиска в JavaScript!
Метки:
Поделиться публикацией
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 18
  • +5
    Хм… у вас отрезок разделённый на 30 равных частей, координаты его начала и конца, координаты курсора. Вы уверены, что вам нужен поиск, чтоб определить к какой из частей, курсор находится ближе?
    • –1
      согласен с автором статьи, что если объем данных большой, то использование бинарного поиска будет вполне оправдано. Здесь же простой пример где просто для наглядности показано как это работает
      • 0
        да при построении графика хеш построить по y по пикселям и всё, один фиг он квантует данные для отрисовки.
        • 0
          блин, реально и хеш не нужен, ниже уже указали как правильно, ступил
        • +6
          Здесь же простой пример
          Плохой пример.
          согласен с автором статьи, что если объем данных большой
          То есть бинарный поиск будет быстрее чем i = Math.round(P/ (L / C)), где:
          • i — индекс для svgData (начинается с 0)
          • L — длинна графика
          • С — Количество отрезков на графике
          • P — координата курсора относительно начала графика

          Опять же, если количество отрезков будет больше, чем количество пикселей, наглядность будет совсем хромать и придётся их группировать, чтоб хотя-бы отрезки по 1px получить.
          • 0

            Ещё в статье не рассказано про интерполяционный поиск.
            В нем надо строку


            const middle = Math.floor((start + (end - start)/2);

            заменить на


            const middle = Math.round(start + (target - data[start].svgX) * (end - start)/ (data[end].svgX - data[start].svgX))

            Если данные в массиве расположены более менее равномерно, то такой поиск будет эффективнее. В крайнем случае формула вырождается в ту, что привели выше.

      • +9
        Простите, а что в материале (несмотря на то, что это перевод — я бы даже сказал особенно учитывая то, что это перевод) заслуживает публикации на хабре? Тема базовая, я бы даже сказал, примитивная, уровень подачи, объяснения материала тоже не выделяется.
        • –1
          Повторение — мать учения. Да, тема не сложная, согласен. Но думаю найдется достаточно людей, кому как и мне будет интересно вспомнить университетские знания.
          • 0
            Для того, чтобы её вспомнить, есть множество аналогичных или более содержательных материалов.
            • 0
              Вы всегда можете помочь читателям Хабра и опубликовать эти более полезные статьи. Либо же оставить ссылки на оригиналы для заинтересовавшихся людей.
              Автору же в любом случае спасибо за потраченное время и приложенный труд.
          • –2
            Фильтратор статтей свое дело знает. Наверное это ООООЧЕНЬ страшно увидеть статью о бинароном поиске в своей ленте. Бедьняжечка
            • –1
              Получить два комментария, которые сводятся к «да пошёл ты», от профилей с нулевой кармой и историей, и которые подписаны только на компанию, в блоге которой раньше публиковался автор этого поста — это, кхм, заставляет задуматься.
              • +1
                Как бы это помягче, но, «Чья бы корова..») Хоть и в общем согласен с вашим комментом, но не в карме дело.
                • 0
                  Не спорю, у меня профиль здесь тоже тухлый, но чуть более живой на ГТ. Плюс я по нику в сети ищусь легко. И я не подписан на одну компанию. :)
          • +7
            Извините, но пост ужасен. Во-первых, с такими темпами у нас будут статьи «2+2 на JavaScript». Во-вторых, выкладывать код не самого хорошего качества в обучающей статье — плохо.
            Я молчу про однобуквенные переменные с комментом (это же канон плохого коментария, от которого надо избавляться). Но этот код не будет работать с пустым массивом — банально зациклится. Это одна из ошибок новичка, такое студенты на первом курсе пишут и больше такого не делают. Зачем такое публиковать?
            Кроме того, 100 лет как принянто диапазоны делать открытыми справа, то есть не включать правую границу и не писать уродливое data.length -1. В случае пустого получаем -1, а что это за индекс?
            Ну и в качестве придирки. Плохим тоном, хотя и без последствий в js, является вычисление среднего (a+b)/2. Давно придумали писать a + (b-a)/2, чтобы не иметь переполнений. Да, в js всё double и проблем не будет, но ведь потом так напишут на чём-нибудь ближе к железу.
            • +5
              И ещё, если мы говорим о производительности, то что в коде делает рекурсия? Итеративный вариант точно будет быстрее, да ещё и от переполнения стека защищён. Тут конечно можно сделать через оптимизацию хвостовой рекурсии, но для этого надо код переписать. Так как есть, ни один компилятор не осилит. Да и не думаю, что хоть один движок js это вообще делает.
              • 0
                Спасибо за конструктив, сделал несколько исправлений.
              • 0

                Это гениально — сравнивать перебор (сложность O(n)) и бинарный поиск (O(logn)).


                Если объем данных небольшой, рекурсия может быть медленнее, чем цикл for. При тестировании на jsperf с 10 элементами, рекурсивная функция в среднем на 3% медленнее, чем цикл for. Однако при количестве элементов в 10 000, цикл for на 72% медленнее, чем рекурсивная функция. Это означает, что рекурсия практически в два раза быстрее, чем цикл for, и это огромная экономия времени!

                Голословненько. Где пруфы?


                А бинарным поиском без рекурсии, через while слабо? А вместо монстра Math.floor((a+b)/2) битовый сдвиг, видимо, для нердов и никому уже не нужно.

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