Более общий бинарный поиск в JS

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

Мы все хорошо знакомы с базовым бинарным поиском — если есть отсортированный массив, укажите элемент. Если он существует, вернуть его индекс, если нет, -1.

Это лучше, чем просто обход массива, так как он использует тот факт, что массив сортируется путем разделения поиска на половины, тем самым обеспечивая O(log n) сложность выполнения вместо O(n).

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

function binarySearch(list, value) {
  // start, middle, end
  let start = 0;
  let end = list.length - 1;
  let mid = Math.floor((start + end) / 2);

  // While the middle is not what we're looking for and the list does not have single item
  while (list[mid] !== value && start < end) {
  	// modify search window
    if (value < list[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }

    // new mid value
    mid = Math.floor((start + end) / 2);
  }

  // at the end, either mid is where the value is, or not
  return value !== list[mid] ? -1 : mid;
}

Это хорошо работает для массивов примитивов, скажем, что-то вроде

# Example 1:

binarySearch([1, 2, 3, 4], 1); // => 0

Некоторые проблемы с этим подходом

Но что, если вместо этого вы сделаете что-то вроде

# Example 2:

binarySearch([[1,2],[2,3],[3,4]], [1,2]); //=> -1

или даже,

# Example 3:

function someObject(start, end) {
  this.start = start;
    this.end = end;
};

const A = new someObject(1, 2);
const B = new someObject(3, 4);
const C = new someObject(1, 2);

binarySearch([A, B], C); // => -1

Копание в деталях

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

list[mid] !== value

value < list[mid]

Для более сложных объектов сравнение на равенство может быть не таким прямым, как простая строгая проверка на равенство с помощью ===и сравнение с <. Например, в примере 3 объект A а также C обладал одинаковыми составляющими свойствами. Возможно, мы хотели бы, чтобы их считали равными. Просто делать что-то вроде list[mid] !== value однако этого было бы недостаточно, поскольку технически это «разные» объекты.

Точно так же в примере 2 нет никакого смысла в чем-то вроде [1, 2] !== [1, 2] или же [1, 2] < [1, 2].

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

Решение?

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

Нам действительно нужно только 3

• функция равенства
• функция сравнения (для проверки меньше)
• функция доступа (на случай, если мы ищем что-то более сложное, чем традиционный массив)

function binarySearch(list, value,
  valueLt = (cmp, value) => cmp > value,
  valueEq = (cmp, value) => cmp === value,
  accessor = (list, idx) => list[idx]
) {
  // start, middle, end
  let start = 0;
  let end = list.length - 1;
  let mid = Math.floor((start + end) / 2);

  // While the middle is not what we're looking for and the list does not have a single item
  while (!valueEq(accessor(list, mid), value) && start < end) {
  	// modify search window
    if (valueLt(accessor(list, mid), value)) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }

    // new mid value
    mid = Math.floor((start + end) / 2);
  }

  // at the end, either mid is where the value is, or not
  return !valueEq(accessor(list, mid), value) ? -1 : mid;
}

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

# Example 4: Example 2 revisited

const valueLt = (cmp, value) => {
  return cmp && cmp[0] > value[0] && cmp[1] > value[1];
};

const valueEq = (cmp, value) => {
  return cmp && cmp[0] === value[0] && cmp[1] === value[1];
};

list = [[1,2], [2,3], [3,4]];
binarySearch(list, [1,2], valueLt, valueEq); // => 0

# Example 5: Example 3 revisited

function someObject(start, end) {
  this.start = start;
    this.end = end;
};

const A = new someObject(1, 2);
const B = new someObject(3, 4);
const C = new someObject(1, 2);

const valueLt = (cmp, value) => {
  return cmp && cmp.start > value.start && cmp.end > value.end;
};

const valueEq = (cmp, value) => {
  return cmp && cmp.start === value.start && cmp.end === value.end;
};

binarySearch([A, B], C, valueLt, valueEq); // => 0

Как мы видим, мы можем определить собственные функции сравнения и равенства, которые позволяют нам обрабатывать разные типы объектов, используя один и тот же алгоритм.

Спасибо за чтение!