javascript - 执行二进制搜索时如何正确显示数组中不存在值

Question

我正在尝试用 JavaScript 实现二进制搜索。我能够返回目标元素的索引，但是，我的程序没有返回“-1”来指示目标值不存在于数组中。例如，如果我有一个 [12, 39, 52, 61, 88, 100] 的数组，并且我将目标值“200”输入到我的二进制搜索函数中，它不会返回“-1”来表示即使我构造了 else 语句来执行此操作，该值也不存在于数组中。谁能告诉我我做错了什么？提前致谢。

我的代码:

function binarySearch(arr, target){
var start = 0;
var end = arr.length - 1;

while(start <= end){

    var mid = Math.floor((start +  end)/2);

    if(arr[mid] < target){
        start = mid + 1;
    }

    else if(arr[mid] === target){
        return mid;
    }

    else if(arr[mid] > target) {
        end = mid - 1;
    }

    else {
        return -1;
      }
    }
  }

var myArr = [12, 39, 52, 61, 88, 100];
binarySearch(myArr, 200);

Answer 1

您需要将-1 的返回值移出while 循环，因为如果循环内没有返回，则您的值还没有找到.所以最后只返回-1。

即使是最后一次检查，您也可以省略，在检查了更小或相等的值之后，剩下的总是更大。

function binarySearch(arr, target) {
    var start = 0,
        end = arr.length - 1,
        mid;

    while (start <= end) {
        mid = Math.floor((start + end) / 2);
        if (arr[mid] < target) {
            start = mid + 1;
            continue;
        } 
        if (arr[mid] === target) {
            return mid;
        }
        end = mid - 1;
    }
    return -1;
}

var myArr = [12, 39, 52, 61, 88, 100];

console.log(binarySearch(myArr, 200));  // -1
console.log(binarySearch(myArr, 12));   //  0
console.log(binarySearch(myArr, 39));   //  1
console.log(binarySearch(myArr, 52));   //  2
console.log(binarySearch(myArr, 61));   //  3
console.log(binarySearch(myArr, 88));  //   4
console.log(binarySearch(myArr, 100));  //  5