引入

二分查找是常见的针对有序数组的查找算法，其查找的时间复杂度为 $O(\log n)$。算法骨架很好理解，但笔者在实践过程中一直对一些细节问题模棱两可，例如 while 循环的边界条件、提前退出、二分答案的下标等。通过查询 STL 源码、文献等方式，笔者找到一个通用方案，解决二分查找的一系列细节问题。

标准二分查找

从标准二分查找讲起，即给定严格递增数组 num 和目标值 target，返回 target 在 num 中的下标，若不存在，则返回 -1。一种可行的 C 语言代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int binary_search(int *num, int *numsSize, int target){
	int left = 0;
	int right = numsSize - 1;
	while(right >= left){ // 循环条件
		int mid = (left+right)/2;
		if(nums[mid] > target)
			right = mid-1;
		else if(nums[mid] < target)
			left = mid+1;
		else 
			return mid; // 提前退出条件
	}
	return -1;
}

在查找过程中使用闭区间[left, right] 表示 target 可能存在的位置，那么循环退出只有两种情况：找到了 target 或者区间长度为 0，分别代码中的提前退出条件和循环条件。其中，循环条件根据区间的开闭性质而有所不同，例如若使用左闭右开区间来表示 target 的位置，那么区间长度为 0 表示为 right == left+1，即循环条件为 right != left+1。
根据上面分析，如果找到了 target，一定会通过提前退出直接返回下标 mid，因此如果通过循环条件正常退出循环，说明目标值在数组中不存在，直接返回 -1。

二分查找左边界

二分查找左边界问题定义为：给定非严格递增数组 nums 和目标值 target，返回向 nums 中插入 target 的最小下标。例如，nums = {1,2,2,3}，target = 2，查找得到的左边界应该为 1。
与标准二分查找类似，使用闭区间[left, right] 表示目标下标所在的区间。为了找到 target，我们可以通过不断压缩 right 的位置来逼近目标。怎么压缩呢？当 nums[mid] != target 时候，压缩方案与标准二分一致；当 nums[mid] == target 时，则是之前没有碰到的情况。以下给出一种解决方案：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int lower_bound(int *num, int *numsSize, int target){
	int left = 0;
	int right = numsSize - 1;
	while(right > left) // 循环条件
	{
		int mid = （left+mid)/2;
		if(nums[mid] == target)
			right = mid;
		else if(nums[mid] > target)
			right = mid-1;
		else 
			left = mid+1;
	}
	return left;
	/* 如果target不存在需要返回-1
	** if(left == numsSize || nums[left]!=target)
	**     return -1;
	** else
	**     return left
	*/
}

当 nums[mid] == target 时，上述方案将 right 更新为 mid，对比标准二分方案，可以发现循环条件不再取等了，并且也不存在提前退出的条件。这是由于我们缩写的 lower_bound 函数返回的 target 插入 nums 的下标，因此当区间长度为 1 时，就找到了返回值，可以停止循环。
有些问题可能会要求当 target 不在 nums 中时，返回 -1，那么在循环结束后，需要检查 nums[left] 是否为目标值。值得注意的是，target 可能插入的位置在是 nums 的最后一位，因此需要检查是否越界。

二分查找右边界

二分查找左边界问题定义为：给定非严格递增数组 nums 和目标值 target，返回向 nums 中插入 target 的最大下标。例如，nums = {1,2,2,3}，target = 3，查找得到的右边界应该为 2。
如果参照 二分查找左边界 中的思想，不断压缩左边界，可以写出一个死循环的有边界查找方案：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int upper_bound(int *num, int *numsSize, int target){
	int left = 0;
	int right = numsSize - 1;
	while(right > left) 
	{
		int mid = （left+mid)/2;
		if(nums[mid] == target)
			left = mid; //压缩左边界
		else if(nums[mid] > target)
			right = mid-1;
		else 
			left = mid+1;
	}
	return right;
}

为什么会死循环呢？这是在某些情况下 left 值和 mid 值相等并且 nums[mid] == target，因此 left 值就一直得不到更新，造成了死循环。为了解决这个问题，我们可以通过让 left = mid+1 保证每次对 left 的值的更新都是有效的。
但上面的操作又引入了一个新的问题：mid 循环退出时，mid 可能指向第一个比 target 大的元素，也可能指向 target，而 right 又大于等于 mid，故 right 的指向是不确定的。既然如此，干脆直接让 right 指向第一个比 target 的元素，最后返回 right-1 即可。那么在上一段修改的基础上，对于 nums[mid]>target 情况，right 更新为 mid 即可。
基于上述思想，二分查找右边界的方案如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int upper_bound(int *num, int *numsSize, int target){
	int left = 0;
	int right = numsSize - 1;
	while(right > left) // 循环条件
	{
		int mid = （left+mid)/2;
		if(nums[mid] == target)
			left = mid+1;
		else if(nums[mid] > target)
			right = mid-1;
		else 
			left = mid;
	}
	return right-1;
}