如何使用递归创建二进制搜索

Question

我试图写一个我以前从未做过的"二分搜索".当搜索的值为6或2时,下面的代码不起作用,我想知道我做错了什么以及如何解决它.

编辑

为了解释它的作用(根据我的理解),二进制搜索要求数组已经排序,然后查找数组的中点索引.例如,如果一个数组有九个索引(0-8),则中间点将是索引4.

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];

然后,算法确定该中点的值是否高于或低于您要搜索的数字.数组一侧的所有元素都不包含搜索到的数字,并且在中点值之前存在的元素只是被删除.如果搜索值为8,则结果为:

[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
array midpoint value: 5
[ 5, 6, 7, 8, 9 ]
array midpoint value: 7
[ 7, 8, 9 ]
array midpoint value: 8

码

//_________________________________________________BEGIN notes

    // Step 1. Get length of array 
    // Step 2. Find mid point
    // Step 3. Compare if mid point is lower or higher than searched number
    // Step 4. lop off unneeded side
    // Step 5. go to step 1
//_________________________________________________END notes

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55];

function getMidPoint(arr, searchNumb) {
    var length = arr.length;
    var midPoint = Math.floor(length / 2);
    var newArr = arr;
    console.log(arr);
    console.log("array midpoint value: " + arr[midPoint]);

    if (arr[midPoint] > searchNumb) {

        var newArr = arr.slice(0, arr[midPoint]);
        return getMidPoint(newArr, searchNumb);

    } else if (arr[midPoint] < searchNumb) {

        var newArr = arr.slice(midPoint, arr.length);
        return getMidPoint(newArr, searchNumb);

    } else {
        return arr
    }
}

Answer 1

语言不可知,这里是递归二进制搜索实现的简化流程,假设我们有一个(最初非空)数组[ARR]和目标[T],其中我们将ARR的中间元素称为M:

// 1. If M == T, return true
// 2. If length of ARR is 0, return false (note: step 1 short circuits, ensuring we only hit step 2 if step 1 evaluates to false)
// 3. If T < M, return the result of the recursion on the lower half of ARR
// 4. If T > M, return the result of the recursion on the the latter half of ARR

以下是执行上述控制流程的解决方案.这类似于本文中已经提出的解决方案,但有一些值得注意的差异:

function binarySearch(arr, target, start=0, stop=(arr.length-1)) {

  let midPoint = Math.floor(((stop-start)/2) + start)

  switch (true) {
    case arr[midPoint] === target:
      return true
    case stop - start === 0:
      return false
    case arr[midPoint] < target:
      return binarySearch(arr, target, midPoint+1, stop)
    case arr[midPoint] > target:
      return binarySearch(arr, target, start, midPoint)
  }
}

让我们解开这个实现的主要区别:

• 切片不再使用:

  我们避免使用Array.prototype.slice,因为它是一个相对昂贵的操作(每次递归调用复制当前数组的一半!)并且算法不需要正常运行.

  代替切片,我们传递了我们将搜索范围缩小到的数组范围的开始和停止索引.这可以让我们的堆快乐,因为它不会与同一(潜在的大量)数组的(可能很多)部分,无常复制混乱.

• 我们传递了两个额外的参数,它们有默认值:

  这些参数(开始和停止)用于跟踪我们当前正在重复使用的数组的范围.它们是切片的替代品!默认参数使我们能够像使用切片时那样调用此递归函数(如果用户在首次调用时不提供显式范围).

• 我们使用switch语句:

  switch语句与if-else链的速度取决于几个因素,最值得注意的是编程语言和每个因素的条件数量.这里使用switch语句主要是为了提高可读性.它是一个控制流程,与我们在这个递归函数中处理的内容相匹配:4个离散的情况,每个都需要不同的操作.此外,少数人对超过3次逻辑测试的if-else语句有罕见的过敏反应.有关JavaScript的switch语句及其性能与if-else的更多信息,请看一下这篇文章:Javascript switch vs. if ... else if else,它链接到这个更具信息性的页面http:// archive.oreilly.com/pub/a/server-administration/excerpts/even-faster-websites/writing-efficient-javascript.html