TommyHu.me | TommyHu.me

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动现在有N份试卷，需要在这N份试卷中找到张三的试卷，我们该如何快速找到呢？要是一份一份的去查找，那么最坏的情况可能要查找N次才可以找得到张三的试卷，显然是不符合期望的那么如果我们将试卷按照姓的首字母进行排序，每次都从N/2处开始查找，若是没匹配到，那么进行判断张三首字母Z是在N/2的左侧还是右侧，然后再在剩余的一半继续按照上述顺序查找，直至找到张三的试卷，这个查找的过程就是二分查找现在有一个数组[1, 2, 3, 12, 22, 34, 45, 51],查找22是否存在这个时候需要定义三个变量分别记录左边界l，右边界r和中间位置c 初始化三个数据

const arr = [1, 2, 3, 12, 22, 34, 45, 51];
let l = 0;
let r = arr.length - 1;
let c = Math.floor((l + r) / 2);

可以得到l = 0，r = 7， c = 3 第一次查找，arr[c]的值为12，小于目标值22，判断左边界l需要右移

l = c + 1;
c = Math.floor((l + r) / 2);

可以得到 l = 4, c = 5 然后进行第二次查找，arr[c]的值为34，大于目标值22，判断右边界r需要左移

r = c - 1;
c = Math.floor((l + r) / 2);

可以得到 c = 4, r = 4 然后进行第三次查找，arr[4]的值为22，于目标值22相等，找到目标值，结束查找根据上述的过程转化为代码：

const bSearch = (arr, target) => {
    let l = 0; // 左边界
    let r = arr.length - 1; // 右边界
    let c; // 中间位置
    let currentValue; // 当前中间位置索引的值
    while (l <= r) {
        c = Math.floor((l + r) / 2);
        currentValue = arr[c];
        if (currentValue === target) {
                // 找到 直接返回
                return c;
        } else if (currentValue > target) {
                r = c - 1;
        } else {
                l = c + 1;
        }
    }

    return -1; // 没有找到
};

测试代码：

const arr = [1, 2, 3, 12, 22, 34, 45, 51];

bSearch(arr, 22); // 4
bSearch(arr, 100); // -1

可以看到查找22符合预期，返回结果4 若是查找100，找不到直接返回-1

作者：Nordon 链接：https://juejin.cn/post/7016511928616878111 来源：稀土掘金著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。