35. Search Insert Position

二刷 06/2022

Version #1 Binary Search

看答案终止条件是 start <= end, 这样start会直接变成比target大的第一个，所以可以直接return start而不需要讨论出界情况

Time O(logN)

Space O(1)

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

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

class Solution {

    public int searchInsert(int[] nums, int target) {

        // Find the first number that larger than or equal to target

        int start = 0, end = nums.length - 1;

        while (start < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {

                return mid;

            }

            if (nums[mid] < target) {

                start = mid + 1;

            } else {

                end = mid;

            }

        }

        return nums[start] >= target ? start : nums.length;

    }

}

一刷

找第一个比target大的index
如果所有的number都比target小，则要加在最后

100.00 %
class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        // first index larger than target
        // If not exist, return 0
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            // [1,3,5,6]
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start + (nums[start] < target ? 1 : 0);
    }
}