二进制搜索 - JS

Question

我正在尝试在 JS 中编写一个二分查找函数，用于查找排序数组中第一次出现的“1”。但是我不明白为什么我在使用 while 循环时会陷入无限循环（我的浏览器崩溃）。

这是我到目前为止写的代码

const arr = [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1,1,1,1];

function findTheOne(arr_start, arr_end, arr) {


    let mid = ((arr_start + arr_end)) / 2
    mid = Math.ceil(mid);

    while (arr_start <= arr_end) {
        if (arr[mid] == 1 && (mid == 0 || arr[mid - 1] == 0)) {
            return mid;
        } else if (arr[mid] == 1) {
            arr_end = mid - 1;
            console.log(arr_end);
        } else {
            arr_start = mid + 1;
        }
    }
}
console.log(findTheOne(0, arr.length - 1, arr));

Answer 1

在你的 while 循环中你永远不会更新 mid 的值您可以将中间代码移到 while 循环中。

const arr = [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1,1,1,1];

function findTheOne(arr_start, arr_end, arr) {

    while (arr_start <= arr_end) {
        let mid = ((arr_start + arr_end)) / 2
        mid = Math.ceil(mid);
        if (arr[mid] == 1 && (mid == 0 || arr[mid - 1] == 0)) {
            return mid;
        } else if (arr[mid] == 1) {
            arr_end = mid - 1;
            console.log(arr_end);
        } else {
            arr_start = mid + 1;
        }
    }
}
console.log(findTheOne(0, arr.length - 1, arr));

Answer 2

您需要在循环内更新 mid 的值。如果您移动函数的前两行，使它们位于循环的开头，您的代码应该可以工作。

二进制搜索 - JS

Binary search - JS

javascript

binary-search