前两天在 V2EX 上看到了这篇文章：挖个坑，作为 python 程序员，面试时要求手写二分查找，可以说不么。自己觉得作为一个正常的程序员，多多少少必须会点算法和数据结构，不仅仅要学会怎么用，也要知道是怎么实现的。与此同时《编程珠玑》的作者 Jon Bentley 也提到：
90%以上的程序员无法正确无误的写出二分查找代码。
今天就谈一下和二分有关的一些算法。
二分查找（Binary Search）
问题
二分查找又叫做折半查找。我们所碰到的问题也很简单：
对于一个已经排好序且元素唯一的数组，如何找到我们需要的值value？
解决思路
想法也很明了：通过不断缩小包含我们要找到的这个值value的范围，我们就能最终找到它。很明显，一开始的范围是整个数组长度，利用中间项的大小和value比较我们可以缩小一半的比较范围，以此类推直到我们找到这个value或者判断这个value不在数组中。通过每次一半一半的筛选，二分查找的时间复杂度就是O（logn）。
（建议大家试着写一下二分查找的代码，看看自己会有什么问题）
二分查找代码如下：
注意到第五行，很多教科书会写 int mid = (left + right) / 2; 这样的取中间值的语句，但是在 left 和 right 都较大的时候会溢出。这个 Bug 在 java.util.Arrays 包中存在了 8 年，所以也希望大家注意下。取中间值可以写成 int mid = left + ((right - left) >> 1); 或者 int mid = right - ((right - left) >> 1);。
了解了实现的过程，回头想一下为何可以不断的二分查找呢？原因也很简单：因为数组已经排好序了，也就是说这个数组满足单调性。这一点很重要，不满足的话也无从下手缩小查找范围的地方了。总之整个数组判断 f(a[i]) =< value / f(a[i]) >= value 的状态结果应该是这个样子的：
NO ... ... NO NO YES YES ... ... YES
应用
二分查找的应用也很广泛，尤其是利用单调性这一点，可以利用他来猜测答案。具体的应用相信很多OJ菊苣都知道，渣渣在这里也就不谈了。
快速幂（Exponentiation by squaring）
问题
问题很简单：
怎样计算一个数 N 的 K 次方？
解决思路
正常的话我们会用一个递归的思路去解决：
这个递归算法再简单不过了，算法时间复杂度是 O（n）。但是如果指数非常大的时候，一方面我们无法用 int 来存储我们的整数了，另一方面计算量实在是太大了。
快速幂算法就是为了解决这个问题，算法思路就是利用了二分法。对于奇数和偶数我们分开考虑即可。
(非递归的也很好写，Have a try！）
应用
- 和矩阵运算有关。计算递推数列
A(n) = C(1)A(n-1) + C(2)A(n-2) + ... + C(k)A(n-k)（其中C(i)为常数）时，若 n 较大的时候，我们往往把它转换成向量和矩阵的乘法进行操作，对矩阵求 n 次乘法往往会用到快速幂。 - 快速幂取模。在 RSA 加密中我们会用到
a^b mod c，当 a 和 b 很大的时候，使用 O（logn）的时间计算 a^b mod c 是非常有必要的，想法类似于快速幂，可自行实现一下。
这篇文章希望大家能够看完后对二分思想有个比较清楚的认识，更希望大家不要写错二分查找哦ԅ(╹﹃╹ԅ)