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.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Solution 1:

Use binary search to find the first occurrence that nums[index] >= target.

We can insert the target at index.

Corner case:

1. target < first element. We insert at index 0.

2. target > last element. We insert at index nums.length.

The time complexity is O(logn) and the space complexity is O(1).



Code:

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

Solution 2:

Use binary search to find the last occurrence that nums[index] < target.

Insert at index + 1.

Corner case:

1. target <= first element. We insert at index 0.

2. target < last element. We insert at index nums.length.

The time complexity is O(logn) and the space complexity is O(1).


Code:

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