javascript - 数组极端情况下的二进制搜索

Question

我正在尝试实现二分搜索，除极端情况外，所有数字都运行良好:

const a = [1,2,3,4,5];

function findNum(arr, num) {
    let start=0, end = arr.length-1, mid = Math.floor((start+end)/2);

    while(start <= end) {
        mid = Math.floor((start+end)/2);
        if(mid===num) return true;
        else if(mid > num) end = mid-1;
        else start = mid+1;
    }
    return false;    
}

console.log(findNum(a, 5));

当我搜索“5”时，它返回 false，而不是 true。我在这里错过了什么？

所有其他情况都按预期正常工作。

Answer 1

您需要检查值，而不是索引。

const a = [1, 2, 3, 4, 5];

function findNum(arr, num) {
    let start = 0,
        end = arr.length - 1,
        mid = Math.floor((start + end) / 2);

    while (start <= end) {
        mid = Math.floor((start + end) / 2);
        if (arr[mid] === num) return true; // take value
        if (arr[mid] > num) end = mid - 1; // take value as well
        else start = mid + 1;
    }
    return false;
}

console.log(findNum(a, 0));
console.log(findNum(a, 1));
console.log(findNum(a, 2));
console.log(findNum(a, 3));
console.log(findNum(a, 4));
console.log(findNum(a, 5));
console.log(findNum(a, 6));