Search Insert Position

Q:
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
A:   
***************Iteratively check ************

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

^^^^^^^^^^^^^^  逐个检查就行******************

public class Solution {
    public int searchInsert(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }
        if (target <= A[0]) {
            return 0;
        }
        if (target > A[A.length - 1]) {
            return A.length;
        }
        // NOW target falls in the range of array
        for (int i = 0; i < A.length - 1; i++) {
            if (A[i] < target && A[i + 1] >= target) {
                return i+1;
            }
        }
        return -1; // this should be never reached
    }
}

Mistakes:
1: 当找到 A[i] < target  && A[i+1]>= target的时候，我们应该返回的是i+1  ,而不是i
2： for (int i = 0; i < A.length -2; i++) {      这里，减2是不对的， 应该是 - 1.  我们这里，光考虑不要后面的了。
3： 首先检查数组最后一个数： 应该是小于target  而不是像 A[0]那样， 是<= 的情况。
4：

------------------2nd pass--------------  Recursive ------

public class Solution {
    public int searchInsert(int[] nums, int target) {
        // find the first position i, s.t nums[i]>=target, and return i
        return helper(nums,0,nums.length-1, target);
    }
    private int helper(int[] A , int begin, int end, int target){
        if(begin  > end){ // invalid
            return begin;
        }
        int mid = (begin + end)/2;
        if(A[mid]>=target){
            return helper(A,begin,mid-1,target);
        }else{
            return helper(A,mid+1, end, target);
        }
    }
}

Learned: