Search Insert Position

Question:

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

Difficulty: Medium

Link: https://leetcode.com/problems/search-insert-position/description/

Solution:

Firstly, think about the template of Binary Search. We use it to find a target number in a given array.

Let's see the example:

1. We try to find a place to insert 5 in [1, 3, 5, 6]. The position is 2 where there's an element equals to 5. [1, 3, (5), 5, 6]
2. We try to find a place to insert 2 in [1, 3, 5, 6]. No element is equals to 2, we find 3 which is in 2nd place. It is the first element that greater than 2. [1, (2), 3, 5, 6]
3. We try to find a place to insert 7 in [1, 3, 5, 6]. All of the elements in the given array is smaller than 7, so the position to insert 7 is behind 6. [1, 3, 5, 6, (7)]
4. We try to find a place to insert 0 in [1, 3, 5, 6]. All of the elements in the given array is greater than 0, so the position to insert is the beginning which is 0. [(0), 1, 3, 5, 6]

Finding: now we can find, the place to insert is actually the first element that greater or equals to the target element. Corner case is when target is larger than all given elements, means when you can't find any element greater or equals than the target, the answer will be the arr.length + 1.

How do we find the first one that equals or greater than the target? We divide into 2 conditions:

(keep this in mind: we are looking for the first element that greater or equal to our target)

1. nums[mid] >= target, this means nums[mid] could be our final answer (the first one), or could be on the right of our final answer (not the first one). In another word, our final answer is nums[mid] or an element on the left side. So we shrink the size of array by moving end to mid. (can't do mid-1, since it might cut our final answer out)
2. nums[mid] < target, this means nums[mid] is smaller than our final answer. And we know we dont want anything that smaller (we need element that greater or equals to target). So we can make sure that nums[mid] is not our final answer. Then let it go! The final answer should be on the right of nums[mid] (not includes nums[mid]). So we can shrink the size of array by moving start to mid+1; (If you move it to mid, it won't effect the final result but will do harm to efficiency)

Time: O(logN), N is the length of nums

Space: O(1)

Code:

public class Solution {
    public int SearchInsertPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        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 + 1;
            }
        }

        if (nums[start] >= target) {
            return start;
        } else if (nums[end] >=target) {
            return end;
        } else {
            return end + 1;
        }
    }
}