Бінарний пошук у JavaScript

Що таке бінарний пошук?

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

Тепер порівняємо це збінарним пошуком.

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

Якщо вона менша, ми можемо видалити праву половину масиву.
Якщо вона більша, ми можемо видалити ліву половину масиву.
Якщо воно рівне, ми повертаємо значення

Але суть у тому, що масив має бути відсортований, тобто значення мають бути в правильному порядку, щоб бінарний пошук працював правильно.

Працюючи з великими обсягами даних набагато ефективніше використовувати бінарний пошук, оскільки з кожної ітерації видаляється половина непотрібних значень масиву, а чи не одне невідповідне значення.

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

Як це працює?

У нас є масив усіх координат та відповідних їм даних. Координати знаходяться всередині об'єкта, і кожен об'єкт має svgX ключ. Виглядає це приблизно так:

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

Ось як виглядає код циклу for. Ми перебираємо всі значення svgX, і об'єкт зі значенням, яке ближче до координати X курсору миші, це той об'єкт, дані якого ми хочемо показати.

Спочатку ми отримуємо ширину нашого svg елемента та створюємо порожній об'єкт для зберігання нашої найближчої точки.

Потім ми перебираємо масив даних. Кожне svgX значення об'єкта нашому масиві порівнюється з координатою X курсора миші. Якщо поточна ітерація циклу має значення ближче до курсора, ніж будь-яка інша ітерація, то ця точка встановлюється як наша найближча точка.

За невеликої кількості даних цей метод є відносно швидким. Однак, якщо ми маємо великий обсяг даних, цей варіант вже не буде таким ефективним.

Бінарний пошук

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

Нам потрібно п'ять основних складових для нашого бінарного пошуку:

data -дані.Масив об'єктів.
target -мета.Розташування курсору миші (координата x).
start -початок.Початкова позиція в масиві для поточної ітерації бінарного пошуку.
еnd -кінець.Кінцева позиція в масиві для поточної ітерації бінарного пошуку.
мiddle -середина.Середина масиву для поточної ітерації бінарного пошуку.

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

Як видно з наведеного вище коду в рядку 10, при запуску бінарного пошуку передаємо на вхід весь масив даних, об'єкт миші, початкову позицію 0 і кінцевупозицію, рівну повному розміру масиву:

Коли ми маємо наші дані, середину масиву знайдемо шляхом поділу на два, суми з початкової і кінцевої позицій. Щоб уникнути дріб, результуюче число округляється вниз:

Таким чином, середина 0 + (4-0)/2 округлена вниз = 2:

Ми пам'ятаємо, що для цього прикладу наше цільове значення дорівнює 3,7. Після того, як ми знайшли середню позицію, ми перевіряємо, чи вона дорівнює нашому цільовому значенню. Якщо це так, ми повертаємо об'єкт і все готове!

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

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

Ця умова спрацює, коли наш масив зменшився до двох фінальних значень і наша мета знаходиться між ними. І тут ми повертаємо ближнє значення.

На поточну ітерацію умова поверне false.

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

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

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

Наш новий виклик binarySearch() буде шукати від позиції 2 до data.length-1:

Функція знаходить нову середню позицію data[3]:

Оскільки наше цільове значення3,7менше середнього значення4, ми відкидаємо праву сторону масиву та повертаємо новий виклик функції binarySearch(). На цей раз наша початкова позиція залишається data[2], а кінцева позиція змінюється середню data[3].

Ми дійшли до моменту, коли наша умова виконається:

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

Тест швидкості

Якщо обсяг даних невеликий, рекурсія може бути повільнішою за цикл for. При тестуванні на jsperf з 10 елементами, рекурсивна функція в середньому на 3% повільніша, ніж цикл for.Однак при кількості елементів в 10 000, цикл for на 72% повільніше, ніж рекурсивна функція.Це означає, що рекурсія практично вдвічі швидше, ніж цикл for, і це величезна економія часу!

Хардкорна конфа за С++. Ми запрошуємо лише профі.