public class Solution {

    /**

     * param A : an integer sorted array

     * param target :  an integer to be inserted

     * return : an integer

     */

    public int searchInsert(int[] A, int target) {

        if(A == null) return -1;

        if(A.length == 0) return 0;

        int left = 0; int right = A.length - 1;

        while(left + 1 < right){

            int mid = (left + right) / 2;

            if(A[mid] == target){

                return mid;

            }

            else if(A[mid] < target){

                left = mid;

            }

            else if(A[mid] > target){

                right = mid;

            }

        }

        if(A[left] >= target){

            return left;

        }

        else if(A[right] < target){

            return right + 1;

        }

        else return right;

    }

}