Бинарный поиск, метод рекурсии, возвращающий неверный вывод - js

Question

Я пытаюсь выполнить базовый c бинарный поиск значения в массиве с использованием метода рекурсии. Я использовал итеративный метод в этом же массиве и получил правильный вывод. Но этот код возвращает false (элемент не находится в массиве) независимо от того, находится ли вход в массиве или нет.

let recursionFunction = function (arr, x, start, end) {
  if (start > end) {
    return false
  }
  let mid = Math.floor((start + end)/2)
  if (arr[mid] == x) {
    return true
  }
  if (arr[mid] > x) {
    return recursionFunction(arr, x, start, mid-1)
  } else {
    return recursionFunction(arr, x, mid+1, end)
  }
}
let x = 91
let arr = [28, 91, 30, 33, 2, 7, 88, 90, 70, 44, 40, 41]
if (recursionFunction(arr, x, 0, arr.length-1)) {
  console.log("element is found in arr")
} else {
  console.log('element is not found in arr')
}

Answer 1

Вам просто нужно отсортировать массив перед выполнением двоичного поиска. Поэтому в строке 16, где вы создаете данные примера, просто добавьте .sort() в конец.

Бинарный поиск невозможен с несортированным набором данных.

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

Answer 2

Как указано в комментариях, ваш массив должен быть упорядочен для того, чтобы бинарный поиск работал, подумайте о шагах для предоставленного вами массива ([28, 91, 30, 33, 2, 7, 88, 90, 70, 44, 40, 41])

, на первом шаге он предпримет значение в середине массива (7), которое будет меньше, чем значение, которое вы смотрите (91), затем оно уменьшит ваш массив до ([88, 90, 70, 44, 40, 41]), а затем вы можете заметить, почему ваш элемент не найден .

использование sort перед вашим массивом решает проблему:)

5 7 8 70 10 40 11 41 элемент не найден в arr

let recursionFunction = function (arr, x, start, end) {
  if (start > end) {
    return false
  }
  let mid = Math.floor((start + end)/2)
  console.log(mid, arr[mid])
  if (arr[mid] == x) {
    return true
  }
  if (arr[mid] > x) {
    return recursionFunction(arr, x, start, mid-1)
  } else {
    return recursionFunction(arr, x, mid+1, end)
  }
}
let x = 91
// with sort, it will work.
let arr = [28, 91, 30, 33, 2, 7, 88, 90, 70, 44, 40, 41].sort();
if (recursionFunction(arr, x, 0, arr.length-1)) {
  console.log("element is found in arr")
} else {
  console.log('element is not found in arr')
}

Answer 3

Ваш массив должен быть отсортирован для двоичного поиска. Он проверяет, находится ли 91 посередине, нет, поскольку 91 больше 7, он проверяет [mid + 1, end].