Как написать кастомный findIndex с бинарным поиском?

Question

[Евгений Журов]

Хочу написать кастомный метод массива findIndexBinary, реализующий бинарный поиск элемента с возвратом его индекса. Но не могу понять, как внутри самого метода получить доступ к заданному элементу.

В чистом виде сама функция выглядит так

const searchBinary = (nums, target) => {
  let left = 0
  let right = nums.length - 1
  let middle

  while (left <= right) {
    middle = Math.round((right - left) / 2) + left

    if (target === nums[middle]) {
      return middle
    } else if (target < nums[middle]) {
      right = middle - 1
    } else {
      left = middle + 1
    }
  }

  return -1
}

Я пробовал сделать следующий вариант (см ниже). И если с первым if внутри while все понятно, то что должно быть в else if? Пока хардкодом продублировал внутри while константу target, но ведь от нее нужно как-то избавиться. Иначе говоря, как получить этот target, чтобы сравнить с this[middle] ведь он внутри коллбэк функции?

Array.prototype.findIndexBinary = function(callback) {
  let left = 0
  let right = this.length - 1
  let middle
  
  while (left <= right) {
    middle = Math.round((right - left) / 2) + left
    
    // Этой константы тут, разумеется, быть не должно
    const target = 10
    
    if (callback(this[middle], middle, this)) {
    // вместо if (target === this[middle]) {
      return middle
      // а вот что должно быть в качестве условия else if - непонятно
    } else if (target < this[middle]) {
      right = middle - 1
    } else {
      left = middle + 1
    }
  }

  return -1
}

const elementIndex = nums.findIndexBinary(el => el === 10)

Answer 1

[Wataru]

Есть два варианта. Первый - функция возвращает -1, 0 или 1 сравнивая 2 элемента в зависимости от того, какой меньше или если они равны.

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

Тогда равнество можно сделать так: !f(a,b) && !f(b,a). А второе условие просто заменяется на один вызов функции.

Comments

[Alexandroppolus]

Тогда равнество можно сделать так: !f(a,b) && !f(b,a)

равенство лучше оставить в "else", тогда будет только 2 вызова (или один в лучшем случае)

if (f(a, b)) {
  // a < b
} else if (f(b, a)) {
  // a > b
} else {
  // a === b
}

[Евгений Журов]

Wataru , Alexandroppolus Не могу никак понять) Мне нужно изначально в коллбэке проверять не равенство, а больше/меньше?

При проверке на равенство, получается, нет разницы между f(a, b) и f(b, a) - и так, и так вернется false. Значит, в самом коллбэке должна делаться проверка не на равенство (el => el === 10), а на больше/меньше, но тогда не понимаю, как именно это должно выглядеть, чтобы еще и не вводило в заблуждение при чтении кода. Цель же - именно получить индекс элемента, если элемент равен заданному числу (el === 10). Не пойму, как это описать в категориях больше-меньше.

[Wataru]

Евгений Журов, Да, callback должен проверять только меньше. Меняя местами параметры вы можете проверять и больше. Если не меньше и не больше, то тогда оно равно.

Код приведенный Alexandroppolus с комментариями весьма понятен и читабелен. Если коллбак еще и назвать IsLessThan, тогда вообще все кристально ясно будет. А то, что ветки (равно, меньше, больше) местами переставлены нисколько не усложнаяет алгоритм бинпоиска.

[Евгений Журов]

Wataru, да, но просто тогда непонятно как называть сам метод)
"IsLessThan", равно как и само условие el < 10 скорее вводит в заблуждение относительно того, что метод в действительности делает. Я бы подумал, увидев его, что метод возвращает отфильтрованный массив элементов, которые меньше 10-ти. Либо, что он возвращает true/false, если в массиве есть/нет элемент меньше 10-ти. Но то, что он возвращает индекс элемента 10 - совсем неочевидно.
К примеру, нативный findIndex выглядит так:
array.findIndex(el => el === 10)
И при чтении сразу понятно, что возвращается не что иное, как индекс элемента, если элемент 10 есть в массиве.
В любом случае, спасибо за помощь. Но все-таки подумаю еще, как реализовать именно в виде (el => el === 10). Попробую какую-нибдуь другую реализацию самого алгоритма придумать.

[Wataru]

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

Думаю, если в название вставить binarysearch то станет понятно, что ищется не первый меньгий 10.

[Alexandroppolus]

Евгений Журов, для findIndex достаточно проверить на равенство. Потому что он тупо обходит массив и проверяет каждый элемент. А для бинарного поиска не обойтись без сравнения "меньше". В этом ключевая разница.

Полагаю, удобнее будет первый вариант, где колбэк возвращает -1, 0 или 1 (точнее, вместо -1/1 могут быть любые значения меньше/больше нуля). Такой колбэк, например, использует стандартная js функция сортировки массива, это устоявшийся привычный кейс.

[Евгений Журов]

Alexandroppolus, Wataru, да, все-таки, думаю вы правы. Тут действительно не обойтись без проверки на меньше. Спасибо!