35. 搜索插入

704的变体，就改了一个地方：如果找不到就返回应该插入的位置。看看704原来代码：

cpp

class Solution {
  public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, middle;
        while (left <= right) {
            middle = (left + right) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = left + 1;
            } else {
                return middle;
            }
        }
        return -1; // here
    }
};

把return -1改掉即可。问题在于，return谁呢？

首先，我们必须明白，这个return什么时候才会发生。很显然，等于条件没有触发，最后是搜索不下去了，出循环了才来的这里。那么搜索为什么搜不下去了？因为left>right了，此时left和right的顺序颠倒，left在右边，right在左边，差1,已经构不成闭区间了。

其次，我们看看left和right的实际含义。right什么时候才会改变？nums[middle] > target，而且是right = middle - 1;，这会让right移到middle左边的位置，所以，middle左边的元素，或者说，right及其左边的元素，全部都是小于target的，而right这个位置，就是最后一个小于target的数。同理，left及其右边的元素全部小于target，left这个位置是第一个大于target的数。

所以从直观上感觉，数字应该插入在right和left之间。最终这个位置的下标应该是left或者right+1.

最后，改成return left;或者return right+1;就好了。

cpp

class Solution {
  public:
	int searchInsert(vector<int> &nums, int target)
	{
		int left = 0, right = nums.size() - 1, middle;
		while (left <= right) {
			middle = (left + right) / 2;
			if (nums[middle] > target) {
				right = middle - 1;
			}
			else if (nums[middle] < target) {
				left = middle + 1;
			}
			else {
				return middle;
			}
		}
		return left;
	}
};

35. 搜索插入 ​

35. 搜索插入