Question

link

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

Stats

Frequency 2
Difficulty 2
Adjusted Difficulty 2
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very basic, yet very difficult question. It is not easy to get it correct at first attempt.

Read this blog for more.

My code

public class Solution {
    public int searchInsert(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int len = A.length;
        int left = 0;
        int right = len - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        // now are have a adjacent range [left, right]
        if (target <= A[left]) {
            return left;
        } else if (target <= A[right]) {
            // remember not to miss the == case
            return right;
        } else {
            return right + 1;
        }
    }
}