1. LeetCode 35. 力扣第一题

konosekai / 2023-05-13 / 原文

按照代码随想录的顺序，今天刷了LeetCode 35.搜索插入位置，也是刷的力扣第一题

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

自己思路：

按照闭区间查找。

如果区间里只有两个元素，要找的元素是第二个。

假设区间为[0，1]，left = 0，right = 1。如果循环条件是 left < right，mid = 0，x > 0，left = mid + 1 = 1，区间成了[1，1]。此时就不满足left < right了，就出循环了，不能查找到第二个元素了。

所以循环条件要是 left <= right，就可以查找到第二个元素了。

如果目标值不在数组中，则最后查找的区间会缩小到一个元素的区间，left = right = mid。如果目标值比此元素大，应该插入到下一个位置，执行 left = mid + 1，然后出循环，应该 return left。如果目标值比此元素小，应该插入到当前位置，执行 right = mid - 1，然后出循环，应该 return left。综合起来，要返回应该插入的索引值是left。