LeetCode 35. Search Insert Position

题目：

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 4:

Input: [1,3,5,6], 0
Output: 0

这道题总觉得看着怪眼熟的，给定一个target，让你返回这个target在数组中的index（如果target存在于数组中）或者返回这个target应该插入到数组中的哪个位置（如果target不存在于数组中）。一上来就想到二分法，大方向是对的，但是写代码的过程中有点跑偏了导致没做出来，其实思路很简单，设置一个low和一个high，只要在low<=high的过程中不断比较mid和target的值是否相等，直到low>high都还没找到相等的值的话那就说明target不在数组中，此时返回的low即为应当插入的位置（这个我也觉得很神奇，直觉上这么认为，但并不知道如何证明）。

代码如下，时间复杂度O(n)，运行时间4ms：

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

2020.5.7 更新java版本和二分不完全总结

写另一道题的时候有个要在已排序的数组里找位置的部分给卡着了，我太菜了.jpg 于是翻回了这道题，重新整理一下二分法的思路。

主要就是在于，二分法里的边界条件。我习惯性用left = 0, right = num.size() - 1这样，于是乎在while里面就要left <= right，更新low/high的时候就要low = mid - 1, high = mid + 1。别的方法我就不写了，免得自己把自己绕晕了。

如果是普通的查找，找不到就直接return false就好了。但是如果要查找插入的位置，即第一个不小于目标值的数，则要return low。为啥呢？因为while里面如果是low <= high的话，循环的跳出条件就是low > high，即low肯定在high右边。这时候数值之间的关系是nums[high] < num < nums[low]，所以return low就可以了。

java代码：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (target < nums[mid]) {
                high = mid - 1;
            } else if (target > nums[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return low;
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Search Insert Position.

Memory Usage: 39 MB, less than 100.00% of Java online submissions for Search Insert Position.

后来又实验了一下这个情况[0, 1, 1, 1, 1]，插入1，以上代码会返回2作为插入点，而lc的答案是1。为了能找到第一个插入的位置，需要把第一个if里面的target < nums[mid]改成target <= nums[mid]，不能在==的时候直接return，也就是说相等的时候要继续更新high。更新版的代码：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (target <= nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

而如果要查找最后一个可以插入的位置，则是把<=换成<，也就是如果相等的情况下应该要更新low：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (target < nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

LeetCode 35. Search Insert Position

浏览过的版块