市面上，二分查找算法的实现方法有很多。其共同的特点是，看起来似乎很容易，但是面试的时候，即使是同样的题目却很难复现，更不要说遇到变通的题目。

本文将会帮助你完全掌握binary-search.

1.回到数学的问题的起点

设有连续函数 f(x), 求 f(x) = 0 在区间(a, b) 上的根。我们假设在区间内的解是存在的，则必然有下面的关系：

f(a) < 0 < f(b)

函数 f 在区间a，b内必然至少有一个点为0，由此分情况讨论：

1. f(x) > 0，则 f(x) = 0 的情况在 a 与 x 之间
2. f(x) < 0，则 f(x) = 0 的情况在 x 与 b 之间。

如此循环而不断缩小查找区间，最终达到最小区间，跳出运行。

算法复杂度为：Θ(log(L/T))， 其中L(Length)为区间长度， T(tolerance) 为容差。

2.关于抽象思考

在撰写具体的实现之前，荡开一笔，探讨你的大脑中如何思考 f(x) > 0 这个表达式。

是读作 “f(x) 大于 0” 或者 “f(x) greater than 0" 吗？

比较符号 ">” 是最原始的运算符号，当我们用它思考的时候，大脑就不由自主的陷入到繁琐的细节之中，因此导致我们常常遇到的情况。明明一个算法很简单，比如“冒泡排序”，”插入排序“，一看就懂，但是真要动手写一个时候，往往要耗费半个多小时。

其症结只在于，我们的思考纠缠到了具体的实现上，计算机能够轻松的运行 < > 等运算符号，但是我们用以思考的语言没有将其向更高维度抽象出来。

再进一步思考，“f(x) 大于 0” 对大脑而言究竟是什么意思？ 对，很简单，大于0 是正值。当我们用 “f(x)是正值" 取代”f(x)大于0"之时，大脑与直觉瞬间被激活。因为思考“正值在右边，负值在左边”，比思考“大于0的数就在数轴的右边，而小于0的数字就在数轴数轴的左边”更加符合直觉，更加不需要思考。

由此，定义出positive和negetive两个函数：

function positive(x) { return x > 0; }
function negative(x) { return x < 0; }

虽然很简单，却能帮助大脑从案牍劳形的低级思考中解放出来。

3.算法实现

闲话少叙，直接上算法实现：

function search(f, neg_point, pos_point) {
    let midpoint = average(neg_point, pos_point);
    if (close_enough(neg_point, pos_point)) {
        return midpoint;
    } else {
        let test_value = f(midpoint);
        if (positive(test_value)) {
            return search(f, neg_point, midpoint);
        } else if (negative(test_value)) {
            return search(f, midpoint, pos_point);
        } else {
            return midpoint;
        }
    }
}

第一行中，将average单独拎出来，遵循了与定义positive和negetive相同的逻辑，即在思考过程中不纠缠于初级的表达语言。

function average(a, b) {
  return (x + y) / 2;
}

函数close_enough定义tolerance容差。

function close_enough(x, y) {
    return abs(x - y) < 0.001;
}

定义绝对值：

function abs(x) {
    return x >= 0 ? x : -x;
}

4.测试与验证

先测试求平方根sqrt，比如求数字 7 的平方根：

console.log(search(x => x * x -7, 0, 7));
//: 2.64593505859375
//或者求立方根：
console.log(search(x => x * x * x - 57, 0, 57));
: 3.8482131958007812
//或者求三角函数的值：
console.log(search(x => Math.sin(x) - 1, 0, 1)

或者负责的多元求根公式：

x^3 - 3x^2 - 101 = 0

console.log(search(x => x**3 -3*x**2 - 101, 0, 101)
//求得：
5.900630950927734

最后三角函数的求值：

console.log(search(x => Math.sin(x) - 1, 0, Math.PI/2)）

求得：

 1.570412831597925

验证：

> Math.asin(1)
1.5707963267948966

更进一步的抽象

以上定义的函数search以及验证：

function search(f, neg_point, pos_point)

的过程中，有一步必需的人工操作，就是验证 f(a) 与 f(b) 这两个值是正值还是负值，然后才能带入到方程中的正确位置。

由此，我们将其进一步抽象：

function binary_search(f, a, b) {
    let a_value = f(a);
    let b_value = f(b);
    return negative(a_value) && positive(b_value) ? search(f, a, b)
           : negative(b_value) && positive(a_value) ? search(f, b, a)
           : error("values are not of opposite sign");
}

进一步抽象的方案就能求任何方程的解。