Leetcode: 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

Analysis:
This question is very similar to binary search. The major difference is it will return the index where it would be if the target is not found. In binary search, we simply return the index -1 to indicate that the search fails. 

This problem assumes that no duplicates in the array. We will talk about how this assumption affect the final solution. 

Naive Solution:
A very straight-forward solution is scan the array from the beginning. Compare the target with each array element. If the target is greater than the element, move on. If equals, return the position. If smaller, that is the insertion point. 

public class Solution {
    public int searchInsert(int[] A, int target) {
        // if the array is empty, just insert target into index 0
        if (A.length == 0) return 0;
        
        // iterate the array until the end
        for (int i = 0; i < A.length; i++) {
            if (A[i] >= target) return i;
        }
        
        // insert at the end
        return A.length;
    }
}

Discussion:
The native solution is very simple and neat. It is easy to see that the worst case time complexity is O(n). That is we insert the largest value at end of the array. The space complexity is O(1) since we don't need additional space to store temporary values. 

How about if the array has duplicated elements? In this case, if the target is greater than the element, we should check if its following elements repeats and we insert the target into the last repeated element. 

Better Solution:
Remember this question is closed to the binary search. Can we use this as a hint to devise a better solution? The answer is yes! 

If the target number hits one element in the array, it is exactly the binary search. If not, instead of returning the index as -1, the low pointer is the position it should insert to. So the complexity now becomes O(logn).

public class Solution {
    public int searchInsert(int[] A, int target) {
        return binaryInsert(A, target, 0, A.length - 1);
    }
    
    private int binaryInsert(int[] A, int target, int lo, int hi) {
        if (lo > hi) return lo;
        
        int mid = (lo + hi) / 2;
        if (target < A[mid]) return binaryInsert(A, target, lo, mid - 1);
        else if (target > A[mid]) return binaryInsert(A, target, mid + 1, hi);
        else return mid;
    }
}

Summary:
The problem itself is very simple, but requires necessary familiarity with binary search. So a tip to prepare the code interview is not only stressing the leetcode, but basic algorithms are very important. You are required to write down the bug-free code for the algorithms and get every single detail of them.

Update on 9/29/14:

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

Nine Chapter Solution:

/**
 * Copyright: NineChapter
 * - Algorithm Course, Mock Interview, Interview Questions
 * - More details on: http://www.ninechapter.com/
 */

public class Solution {
    public int searchInsert(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;
        int mid;
        
        if (target < A[0]) {
            return 0;
        }
        // find the last number less than target
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                return mid;
            } else if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (A[end] == target) {
            return end;
        }
        if (A[end] < target) {
            return end + 1;
        }
        if (A[start] == target) {
            return start;
        }
        return start + 1;
    }
}

Discussion:
The mainly idea in the nine chapter solution is the termination condition is lo + 1 >= hi, which means lo and hi points to the same element or adjacent elements. Then the target value could be less than lo, between lo and hi, and greater than hi.  

Update on 1/25/15:

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