二进制搜索，递归方法，返回错误的输出 - js

Question

我正在尝试使用递归方法对数组中的值进行基本的二进制搜索。我在同一个数组上使用迭代方法并获得了正确的输出。但是无论输入是否在数组中，此代码都返回 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

您的数组需要进行排序以进行二分查找。它检查 91 是否在中间，否，因为 91 大于 7，它检查 [mid+1, end].

Answer 2

您只需在执行二进制搜索之前对数组进行排序。因此，在创建示例数据的第 16 行，只需将 .sort() 添加到末尾即可。

无法对未排序的数据集进行二分查找。

我假设您这样做只是为了学习，但我想指出，如果您的列表已排序并执行查找，大多数编程语言将在后台使用二进制搜索。这就是为什么将其理解为一个概念很重要，但您不太可能必须自己实施它。

Answer 3

如评论中所述，您的数组应该排序才能使二进制搜索工作，请考虑您提供的数组的步骤 ([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')
}

二进制搜索，递归方法，返回错误的输出 - js

Binary Search, Recursion Method, Returning the wrong output - js

javascript

recursion

binary-search