[数据结构与算法]二分查找的运用

二分查找又叫折半查找，是一种使用频率很高的查找算法，原理简单，容易上手。
算法如下：

int BinSearch(int A[], int n, int k) {
	int l = 0, r = n - 1, mid;
	while (l <= r) {
		mid = (l + r) / 2;
		if (k == A[mid]) 
			return mid;
		else if (k < A[mid]) 
			r = mid - 1;
		else
			l = mid + 1;
	}
	return -1;  //查找失败
}

这是一本数据结构教材上关于二分查找算法的定义，今天在leetcode上刷题恰好碰到了一道二分查找题，我以为用上面这个模板就完事了，肯定贼简单，谁知这个题竟然隐藏了好几个坑，我改了好几回代码才通过，终究还是我大意了。

题目描述：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

解题思路：
乍一看，这道题和二分查找没啥关系呀，但是仔细观察，我们会注意到这样一个性质：当我们检测到一个版本为正确版本时，则它之前的所有版本均为正确版本，而当我们检测到一个版本为错误版本时，则它之后的所有版本均为错误版本，因为我们会很容易想到二分查找来解决这个问题。

具体来看，分别初始化左右边界为1和n，其中，n为版本的数量，设置好左右边界后，每次我们都根据左右边界找到中间版本，判断其是否为正确版本。若中间版本为正确版本，则第一个出错的版本必将位于该版本的右侧；否则，第一个出错的版本必将位于该版本及该版本的左侧。

复杂度分析：

• 时间复杂度 O(logn)。n为给定版本的数量。
• 空间复杂度 O(1)。只需要常数个变量的空间存储若干变量。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
		int l = 1, r = n;
		int mid;
		while (l < r) {
			mid = l + (r - l) / 2;  //当l和r较大时，使用(l+r)/2容易溢出
			if (isBadVersion(mid)) 
				r = mid;
			else 
				l = mid + 1;
		}
		return l;
	}
};

首先第一个坑就是mid的计算公式了，你以为使用（l+r）/2计算mid就信了，然而结果是这样的，，，

哦豁，结果溢出了，百度了一波，才知道原来使用（l+r）/2计算mid是有风险的，当左右边界l和r都很大时，l+r就很容易超出int的表示范围，此时就会产生溢出，所以以后还是用mid=l+(r-l)稳妥。

第二个坑就是while循环判断条件那里，我第一开始写的是l<=r，谁知道提交后系统直接告诉我超时了，我一脸懵逼，过了好一会我才反应过来，原来我整了个死循环，循环条件应该是l<r，不能包括l=r。