2

Как написать функцию, которая возвращает наименьший индекс, для array[index] == index используя бинарный поиск? В ходе написания функции возникла проблема с тем, что функция возвращает не наименьшее совпадение индекс - значение, а первое найденное, например в середине.

function equals(a) {
  let sortArr = a.slice();
  sortArr.sort((a, b) => a - b);

  let left = -1;
  let right = sortArr.length

  while (right - left > 1) {
    const mid = Math.floor((left + right) / 2)

    if (sortArr[mid] === a.indexOf(sortArr[mid])) {
      return sortArr[mid]
    }
    if (sortArr[mid] > a.indexOf(sortArr[mid])) {
      right = mid
    } else {
      left = mid
    }
  }

  return -1;
}

console.log(equals([-5, 1, 2, 3, 4, 5, 7, 10, 15]))

6
  • похоже a.indexOf(sortArr[mid]) можно заменить на mid
    – Grundy
    Commented 11 авг. 2021 в 11:00
  • А в условиях требуется отсортировать массив перед поиском? Это ведь меняет соотношение индексов и значений элементов исходного массива. Commented 11 авг. 2021 в 13:28
  • @vsemozhebuty, по идее массив на вход подается уже отсортированный, иначе по нему вообще нельзя будет найти
    – Grundy
    Commented 11 авг. 2021 в 13:51
  • Похоже нужно останавливаться не тогда, когда нашел совпадение, а когда нашел совпадение и в проверяемом интервале осталось один или два элемента
    – Grundy
    Commented 11 авг. 2021 в 13:53
  • Если массив уже отсортированный, тогда не совсем понятно, насколько эффективен тут бинарный поиск — не быстрее ли просто проверять все элементы с первого, пока первый же индекс не совпадёт со значением. Commented 11 авг. 2021 в 13:57

0

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Посмотрите другие вопросы с метками или задайте свой вопрос.