二分查找插入点

二分查找不仅可用于搜索目标元素，还可以解决许多变种问题，比如搜索目标元素的插入位置。

无重复元素情况

Question
给定一个长度为n的有序数组nums和一个元素target，数组不存在重复元素。现将target插入数组nums中，并保持其有序性。若数组中已存在元素target，则插入到其左方。请返回插入后target在数组中的索引。

问题一：当数组中包含target时，插入点的索引是否就是该元素的索引？

题目要求将target插入到相等元素的左边，这意味着插入的target替换了原来target的位置。也就是说，当数组包含target时，插入点的索引就是该target的索引。

问题二：当数组中不存在target时，插入点是哪个元素的索引？

进一步思考二分查找过程（m为中点索引）：当nums[m] < target时，这意味着指针i在向大于等于target的元素靠近。同理，指针j始终在向小于等于target的元素靠近。
因此二分结束时一定有：i指向首个大于target的元素，j指向首个小于target的元素。易得当数组不包含target时，插入索引为i。

代码示例如下：

/*二分查找插入点（无重复元素）*/
int binarySearchInsertionSimple(vector<int> &nums, int target){
	int i = 0, j = nums.size() - 1;
	while (i <= j){
		int m = i + (j - i) / 2;
		if (nums[m] < target)
			i = m + 1;
		else if (nums[m] > target)
			j = m - 1;
		else
			return m;  // 找到target 返回插入点 m
	}
	return i;			// 未找到 target，返回插入点 i
}

存在重复元素的情况

假设数组中存在多个target，则普通二分查找只能返回其中一个target的索引，而无法确定该元素的左边和右边还有多少个target。

题目要求将目标元素插入到最左边，所以我们需要查找数组中最左一个target的索引。

实现步骤：

1. 执行二分查找，得到任意一个target索引，记为k。
2. 从索引k开始，向左进行线性遍历，当找到最左边的target时返回。
   

此方法虽然可用，但其包含线性查找，因此时间复杂度为O(n)。当数组中存在很多重复的target时，该方法效率很低。

现考虑拓展二分查找代码。如图所示，整体流程保持不变，每轮现计算中点索引m，再判断target和nums[m]的大小关系，分以下几种情况：

• 当nums[m] < target或nums[m] > target时，说明还没有找到target，因此采用普通二分查找的缩小区间操作，从而使指针i和j向target靠近。
• 当nums[m] == target时，说明小于target的元素在区间[i,m-1]中，因此采用j = m-1来缩小区间，从而使指针j向小于target的元素靠近。

循环完成后，i指向最左边的target，j指向首个小于target的元素，因此索引i就是插入点。

观察以下代码，其中判断分支nums[m] > target和nums[m] == target的操作相同，因此两者可以合并。即便如此，我们仍然可以将判断条件保持展开，因为逻辑更加清晰、可读性更好。

/*二分查找插入点（存在重复元素）*/
int binarySearchInsertion(vector<int> &nums, int target){
	int i = 0, j = nums.size() - 1;
	while (i <= j){
		int m = i + (j - 1) / 2;
		if (nums[m] < target)
			i = m + 1;		// target 在区间 [m+1, j] 中
		else if (nums[m] > target)
			j = m - 1;		// target 在区间 [i, m-1] 中
		else
			j = m - 1;		// 首个小于 target 的元素在区间 [i, m-1] 中
	}
	// 返回插入点
	return i;
}

总的看来，二分查找无非就是给指针i和j分别设定搜索目标，目标可能是一个具体元素（例如target），也可能是一个元素范围（如小于target的元素）。

在不断的循环二分中，指针i和j都逐渐逼近预先设定的目标。