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

如注释中所述，您的数组应该按照二进制搜索的顺序进行排序，想想您提供的数组([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')
}

Answer 2

需要对数组进行排序以进行二进制搜索。它检查91是否在中间，不，然后由于91大于7，它检查[中间+1，结束]。

Answer 3

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

二进制搜索无法使用未排序的数据集。

我想你这样做只是为了学习，但我想指出的是，如果你的列表被排序并执行查找，大多数编程语言都会在引擎盖下使用二进制搜索。这就是为什么把它理解为一个概念很重要，但你不太可能自己实现它。