市面上，二分查找算法的实现方法有很多。其共同的特点是，看起来似乎很容易，但是面试的时候，即使是同样的题目却很难复现，更不要说遇到变通的题目。
本文将会帮助你完全掌握binary-search.
1.回到数学的问题的起点设有连续函数 f(x), 求 f(x) = 0 在区间(a, b) 上的根。我们假设在区间内的解是存在的，则必然有下面的关系：
f(a) < 0 < f(b)
函数 f 在区间a，b内必然至少有一个点为0，由此分情况讨论：
- f(x) > 0，则 f(x) = 0 的情况在 a 与 x 之间
- 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;
}
先测试求平方根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");
}
进一步抽象的方案就能求任何方程的解。
,
