Шаг 1

Давайте напишем простенький бинарный поиск на примере из предыдущей статьи. На входе будем иметь отсортированный в алфавитном порядке список из растений. Напишем функцию, которая будет бинарным поиском искать позицию переданного в неё растения.

import {test} from "./tester";

/*
binarySearch(plants, "Пион") => 5
binarySearch(plants, "Роза") => null
*/
function binarySearch(plants, plant) {
  return null;
}

const plants = [
  "Аспарагус",
  "Гвоздика",
  "Жасмин",
  "Калина",
  "Малина",
  "Пион",
  "Тысячелистник",
  "Хризантема",
  "Шафран",
  "Юкка",
]

test(binarySearch(plants, "Пион"), 5);
test(binarySearch(plants, "Роза"), null);

Шаг 2

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

import {test} from "./tester";

/*
binarySearch(plants, "Пион") => 5
binarySearch(plants, "Роза") => null
*/
function binarySearch(plants, plant) {
  const left = 0;
  const right = plants.length - 1;

  // Стандартная формула для поиска середины отрезка
  const center = Math.floor((right + left) / 2);

  if (center === plant) {
    return center;
  }

  return null;
}

const plants = [
  "Аспарагус",
  "Гвоздика",
  "Жасмин",
  "Калина",
  "Малина",
  "Пион",
  "Тысячелистник",
  "Хризантема",
  "Шафран",
  "Юкка",
]

test(binarySearch(plants, "Пион"), 5);
test(binarySearch(plants, "Роза"), null);

Шаг 3

Вот и всё, первый бинарный поиск написан! Обратите внимание, что при смещении центра влево мы ищем от текущей левой границы до центра, не включая центр. То же самое касается и смещения вправо. С одной стороны, эта микрооптимизация поможет нам чуть быстрее смещать границы, ведь центр мы уже обработали. А с другой, гарантирует нам нарушение условия left < right, ведь если мы не найдем искомое в массиве из одного элемента, то одна из границ гарантированно зайдёт за другую.

import {test} from "./tester";

/*
binarySearch(plants, "Пион") => 5
binarySearch(plants, "Роза") => null
*/
function binarySearch(plants, plant) {
  let left = 0;
  let right = plants.length - 1;

  while (left <= right) {
    const center = Math.floor((right + left) / 2);

    if (plants[center] === plant) {
      return center;
    }

    // Если то, что мы ищем, левее по алфавиту, идем искать в левую часть массива
    if (plants[center].localeCompare(plant) === 1) {
      right = center - 1;
    // иначе идем в другую сторону
    } else {
      left = center + 1;
    }
  }

  return null;
}

const plants = [
  "Аспарагус",
  "Гвоздика",
  "Жасмин",
  "Калина",
  "Малина",
  "Пион",
  "Тысячелистник",
  "Хризантема",
  "Шафран",
  "Юкка",
]

test(binarySearch(plants, "Пион"), 5);
test(binarySearch(plants, "Роза"), null);
test(binarySearch(plants, "Аспарагус"), 0);
test(binarySearch(plants, "Хризантема"), 7);
test(binarySearch(plants, "Юкка"), 9);

File tester.js

const results = document.getElementById('results')

export function test(left, right) {
  const result = document.createElement('li');

  if (left === right) {
    result.innerHTML = "Тест пройден!";
    result.style.color = "green";
  } else {
    result.innerHTML = `Тест не пройден! ${left} не равно ${right}`;
    result.style.color = "red";
  }

  results.appendChild(result);
}