🌂 目录

之前我们学过使用二分法求平方根，也提到了，二分法是一种很有效的编程思路， 本节学习如何使用二分法在已排序的数组中查找指定的元素

进入下一页

🌂 回顾遍历查找

学习数组时，我们实现过一个在数组中查找指定元素是否存在的函数，如下

function exists(arr, x) {
    for (var i = 0; i <= arr.length; i ++) {
        if (arr[i] == x) {
            return true;
        }
    }
    return false;
}
console.log(exists([1, 3, 5, 7, 9], 3));
console.log(exists([1, 3, 5, 7, 9], 6));

该函数能很好的运行，假设数组的长度是 n，那么最多需要查找 n 次就可以确定 x 是否存在。

现在提出一种假设，如果数组里的数字都是已排序好的，那么有没有更快的方法确定 x 是否存在于数组中呢？

进入下一页

🌂 回顾二分法求平方根

求解平方根时，我们使用了二分法，当时的思路是假如一个连续的数字范围，左边界是 l，右边界是 r：

当时使用二分法的条件是：我们查找的范围是一个连续的数字区域，默认是有小到大排序的。

其实二分法的使用条件可以进行扩展，不需要数字必须是连续的，只要要查找的范围有序即可，因为只要有序，那么就可以根据 m 把找找范围分为 大于 m 的部分，和小于 m 的部分。

在数组中，我们可以根据根据索引来分割数据，但数组的索引只能是整数，这就需要对取到的 m 进行取整，之前学过 Math.floor 可以实现向下取整，那么我们寻找数据中点的表达式就如下：

Math.floor(l + (r - l) / 2)

进入下一页

🌂 递归实现二分查找

根据前面的分析，我们能知道，在一个数组里寻找某个元素，可以分解为三部分

上面的思路，写出来后，可以看到，后两个步骤，就是一个很典型的重复计算，而且计算范围一步步缩小，这是 递归 典型的 使用场景，所以我们先看看递归如何实现二分查找。

根据递归的注意事项，再详细描述下过程：

完整的测试代码如下：

function search(arr, x, l, r) {    
    var m;

    // 查找范围为空，表示未找到指定元素
    if (l > r) {
        return false;
    }

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

    if (x > arr[m]) {
        // 向右查找
        return search(arr, x, m + 1, r);
    } else if (x < arr[m]) {
        // 向左查找
        return search(arr, x, l, m - 1);
    } else {
        // 查找到
        return true;
    }
}

var arr = [1, 3, 5, 7, 9, 10, 11, 18, 19, 28, 93, 103, 188];
console.log(search(arr, 103, 0, arr.length - 1));
console.log(search(arr, 99, 0, arr.length - 1));
进入下一页

🌂 关于测试和调试

通常情况，涉及到循环和递归的代码会稍微有些复杂，有时候我们不能一次性写成功，所以可以加一些 调试 性的语句来辅助理解代码运行的过程， 比如在每次函数调用时，把 l, m, r 变量以及 l 和 r 的范围，数组的第 m 个元素的值等打印出来。

console.log(l, m, r, r - l, arr[m]);

这样函数的每次运行，我们应该可以看到 l 到 r 的范围在逐渐的缩小，以及第 m 个元素是否是要查找的元素等信息，总之，你想要了解哪些信息， 你就打印哪些信息。

第二就是为了防止死循环或堆栈溢出，在循环或递归函数里，加一些看起来不可能发生的 “中止条件”，比如在一个 10 个元素的数组里查找一个数，递归函数 不可能调用超过 100 次，如果超过 100次，那肯定是代码执行有问题了。

所以加上这些防护性的中止条件，可以有助于发现代码中的问题，如在函数外定义一个外部变量 i，初始化为 0，在递归函数的开头加入如下代码：

if (i++ > 100) {
    console.log('递归太多了');
    return;
}

另外就是，为了确保代码的正确性，要多准备一些数据进行测试，比如特别大的数，特别小的数，数组中间的数，数组左边界的数，数组右边界的数，数组范围外面的数 等，要尽可能的包含各种情况去测试，才能保证代码尽没有 BUG。

修改后代码如下

var i = 0;
function search(arr, x, l, r) {
    // 辅助调试，防止堆栈溢出
    if (i++ > 100) {
        console.log('递归太多了');
        return;
    }

    var m;

    if (l > r) {
        return false;
    }

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

    // 调试语句，跟踪整个查找过程
    console.log(l, m, r, r - l, arr[m]);

    if (x > arr[m]) {        
        return search(arr, x, m + 1, r);
    } else if (x < arr[m]) {        
        return search(arr, x, l, m - 1);
    } else {        
        return true;
    }
}

// 尽可能多的去测试
var arr = [1, 3, 5, 7, 9, 10, 11, 18, 19, 28, 93, 103, 188];
console.log(search(arr, 103, 0, arr.length - 1));
console.log(search(arr, 99, 0, arr.length - 1));
console.log(search(arr, 1, 0, arr.length - 1));
console.log(search(arr, 188, 0, arr.length - 1));
console.log(search(arr, 200, 0, arr.length - 1));
console.log(search(arr, -1, 0, arr.length - 1));

可以点击运行按钮，查看代码的整个执行过程，看是否和自己理解的一致。

进入下一页

🌂 循环实现二分查找

二分查找，除了用递归实现外，也可以用循环来实现，整个过程是类似的，也需要找中点 m， 只不过是找到后不去递归的调用自己，而是修改循环变量 l 和 r，动态的改动循环的范围， 每一次循环的范围都在逐步的缩小，直到循环范围为空，或中点即是要找的元素。

var i = 0;
function search(arr, x, l, r) {    
    var m ;
    while (l <= r) {
        if (i++ > 100) {
            console.log('循环太多了');
            return;
        }

        m = Math.floor(l + (r - l) / 2);
        console.log(l, m, r, r - l, arr[m]);

        if (x > arr[m]) {
            l = m + 1;
        } else if (x < arr[m]) {
            r = m - 1;
        } else {
            return true;
        }
    }

    return false;
}

var arr = [1, 3, 5, 7, 9, 10, 11, 18, 19, 28, 93, 103, 188];
console.log(search(arr, 103, 0, arr.length - 1));
console.log(search(arr, 99, 0, arr.length - 1));
进入下一页

小结

恭喜闯关成功，今天学习用二分法查找数组里是否存在指定元素，代码很简短，但理解起来稍有复杂，所以要学习一定的调试 技巧来辅助理解和调试代码。

完成本节学习