二进制搜索，递归方法，返回错误的输出-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 78 7010 4011 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')
}