二分查找插入点
二分查找不仅可用于搜索目标元素，还可以解决许多变种问题，比如搜索目标元素的插入位置。
无重复元素情况
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;elsereturn m; // 找到target 返回插入点 m}return i; // 未找到 target，返回插入点 i
}
存在重复元素的情况
假设数组中存在多个target，则普通二分查找只能返回其中一个target的索引，而无法确定该元素的左边和右边还有多少个target。
题目要求将目标元素插入到最左边，所以我们需要查找数组中最左一个target的索引。
实现步骤：
- 执行二分查找，得到任意一个
target索引，记为k。 - 从索引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] 中elsej = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中}// 返回插入点return i;
}
总的看来，二分查找无非就是给指针i和j分别设定搜索目标，目标可能是一个具体元素（例如target），也可能是一个元素范围（如小于target的元素）。
在不断的循环二分中，指针i和j都逐渐逼近预先设定的目标。
