这是 数据结构和算法面试题系列的下半部分，这部分主要是算法类 包括二分查找、排序算法、递归算法、随机算法、背包问题、数字问题等算法相关内容。本系列完整代码在 github 建了个仓库，所有代码都重新整理和做了一些基本的测试，代码仓库地址在这里： shishujuan/dsalg: 数据结构与算法系列汇总，如有错误，请在文章下面评论指出或者在 github 给我留言，我好及时改正以免误导其他朋友。
文章末尾有系列目录，可以按需取阅，如果需要测试，亦可以将仓库代码 clone 下来进行各种测试。如有错误或者引用不全、有侵权的地方，请大家给我指出，我好及时调整改正。如果本系列有帮助到你，也欢迎点赞或者在 github 上 star✨✨，十分感谢。
数据结构和算法面试题系列—二分查找算法详解 0.概述二分查找本身是个简单的算法，但是正是因为其简单，更容易写错。甚至于在二分查找算法刚出现的时候，也是存在 bug 的（溢出的 bug），这个 bug 直到几十年后才修复（见《编程珠玑》）。本文打算对二分查找算法进行总结，并对由二分查找引申出来的问题进行分析和汇总。若有错误，请指正。本文完整代码在 这里 。
1.二分查找基础相信大家都知道二分查找的基本算法，如下所示，这就是二分查找算法代码：
/** * 基本二分查找算法 */ int binarySearch(int a[], int n, int t) { int l = 0, u = n - 1; while (l <= u) { int m = l + (u - l) / 2; // 同（l+u）/ 2，这里是为了溢出 if (t > a[m]) l = m + 1; else if (t < a[m]) u = m - 1; else return m; } return -(l+1); } 复制代码算法的思想就是：从数组中间开始，每次排除一半的数据，时间复杂度为 O(lgN)。这依赖于数组有序这个性质。如果 t 存在数组中，则返回t在数组的位置；否则，不存在则返回 -(l+1)。
这里需要解释下为什么 t 不存在数组中时不是返回 -1 而要返回 -(l+1)。首先我们可以观察 l 的值，如果查找不成功，则 l 的值恰好是 t 应该在数组中插入的位置。
举个例子，假定有序数组 a={1, 3, 4, 7, 8}， 那么如果t = 0，则显然t不在数组中，则二分查找算法最终会使得l = 0 > u=-1退出循环；如果 t = 9，则 t 也不在数组中，则最后 l = 5 > u = 4 退出循环。如果 t=5，则最后l=3 > u=2退出循环。因此在一些算法中，比如DHT（一致性哈希）中，就需要这个返回值来使得新加入的节点可以插入到合适的位置中，在求最长递增子序列的 NlgN 算法中，也用到了这一点，参见博文最长递增子序列算法。
还有一个小点就是之所以返回 -(l+1) 而不是直接返回 -l 是因为 l 可能为 0，如果直接返回 -l 就无法判断是正常返回位置 0 还是查找不成功返回的 0。
2.查找有序数组中数字第一次出现位置现在考虑一个稍微复杂点的问题，如果有序数组中有重复数字，比如数组 a={1, 2, 3, 3, 5, 7, 8}，需要在其中找出 3 第一次出现的位置。这里3第一次出现位置为 2。这个问题在《编程珠玑》第九章有很好的分析，这里就直接用了。算法的精髓在于循环不变式的巧妙设计，代码如下：
/** * 二分查找第一次出现位置 */ int binarySearchFirst(int a[], int n, int t) { int l = -1, u = n; while (l + 1 != u) { /*循环不变式a[l]<t<=a[u] && l<u*/ int m = l + (u - l) / 2; //同（l+u）/ 2 if (t > a[m]) l = m; else u = m; } /*assert: l+1=u && a[l]<t<=a[u]*/ int p = u; if (p>=n || a[p]!=t) p = -1; return p; } 复制代码算法分析：设定两个不存在的元素 a[-1]和 a[n]，使得 a[-1] < t <= a[n]，但是我们并不会去访问者两个元素，因为(l+u)/2 > l=-1, (l+u)/2 < u=n。循环不变式为l<u && t>a[l] && t<=a[u] 。循环退出时必然有 l+1=u, 而且 a[l] < t <= a[u]。循环退出后u的值为t可能出现的位置，其范围为[0, n]，如果 t 在数组中，则第一个出现的位置 p=u，如果不在，则设置 p=-1返回。该算法的效率虽然解决了更为复杂的问题，但是其效率比初始版本的二分查找还要高，因为它在每次循环中只需要比较一次，前一程序则通常需要比较两次。
举个例子：对于数组 a={1, 2, 3, 3, 5, 7, 8}，我们如果查找 t=3，则可以得到 p=u=2，如果查找 t=4，a[3]<t<=a[4]， 所以p=u=4，判断 a[4] != t，所以设置p=-1。 一种例外情况是 u>=n, 比如t=9，则 u=7，此时也是设置 p=-1.特别注意的是，l=-1，u=n 这两个值不能写成l=0，u=n-1。虽然这两个值不会访问到，但是如果改成后面的那样，就会导致二分查找失败，那样就访问不到第一个数字。如在 a={1，2，3，4，5}中查找 1，如果初始设置 l=0，u=n-1，则会导致查找失败。