Search Insert Position

Problem

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

Regular Linear Solution

public class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;
        int index = 0;
        for (int num : nums) {
            if (target <= num) break;
            index++;
        }
        return index;
    }
}

Binary Search Solution: Make use of Sorted Property in Given Array

public class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null) return 0;
        int start = 0, end = nums.length;
        while (start < end) {
            int mid = (start + end) / 2;
            if (target > nums[mid]) start = mid + 1; //cannot just set to mid, since target != nums[mid] already 
            else end = mid;
        }
        return start;
    }
}

Analysis

A typical Binary Search Problem
Since the given array is already sorted, using binary search will be more appropriate
Complexity:

• Time: O(n), both both solutions
• Space: O(1), no extra space used in both solutions