力扣HOT100之二分查找：35. 搜索插入位置

这道题属于是二分查找的入门题了，我依稀记得一些二分查找的编码要点，但是最后还是写出了一个死循环，无语(ˉ▽ˉ；)…又回去看了下自己当时的博客和卡哥的视频，这才发现自己分情况只分了两种，最后导致死循环。。。下面直接说思路。本题我们采用左闭右开的二分查找法，左区间的搜索范围为[left, mid)，而右区间的搜索范围为[mid, right)，我们要确保这两个查找区间在初始状态下覆盖整个数组的元素，因此left初始化为0，right初始化为nums.size()，而不是nums.size() - 1，下面来讨论区间的更新情况：

1. 当nums[mid] > target时，则右区间内所有的元素都比target大，插入位置应当在左区间内，因此我们将right赋值为mid（因为nums[mid] > target，所以原来的nums[mid]不应包含在区间内，right赋值为mid而不是mid - 1）
2. 当nums[mid] < target时，则左区间内所有元素都比target小，插入位置应当在右区间内，因此我们将left赋值为mid（因为nums[mid] < target，新的区间不应当继续包含nums[mid]，left赋值为mid + 1而不是mid）
3. 当nums[mid] == target时，说明我们在数组中找到了与target值一样的元素，根据输入样例，我们直接将元素插入当前位置，原来的元素后移一位即可，所以我们直接返回mid。
   循环条件是查找区间合法，对于左开右闭的区间，我们必须要保证里面至少有一个元素，因此left不能等于right，必须要保证left < right，左闭右开的区间才是合法的。
   当循环正常结束，一定是数组中没有与target相等的元素，最终触发left == right，退出循环，此时left和right返回哪个都可以，此时nums[left]对应的是数组中第一个大于target的元素，在此处插入，则该位置及以后的元素向后移一位，依然能保证插入后有序。

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size();int mid;//使用左闭右开的找法//左边的查找范围为[left, mid),右边的查找范围为[mid, right)//对于左闭右开的区间，左右端点的差值至少为1才合法while(left < right){mid = (left + right) / 2;if(nums[mid] > target) //插入位置在左区间内right = mid;else if(nums[mid] < target)left = mid + 1;else return mid; }return left;}
};