在数组中进行二分查找的边界情况

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。我在这里漏了什么吗？ 其他所有情况都正常工作。

- TechnoCorner

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));

- Nina Scholz