Binary Search Solution - Search Insert Position

The idea is to implement binary search. Notice that it is very possible that target is not in the array, so add one more end condition that if end-begin < 2, if target is not any of them, calculate the position for return.

public class Solution {
    public int searchInsert(int[] A, int target) {
        if(A == null || A.length == 0){
            return 0;
        }
        return findBST(A, 0, A.length - 1, target);
    }
   
    private int findBST(int[] A, int start, int end, int target){
       
        if(A[start] == target){
            return start;
        }
        if(A[end] == target){
            return end;
        }
       
        int median = (start + end) / 2;
        if(A[median] == target){
            return median;
        }
       
        if(end - start < 2){
            if(target > A[end]){
                return end + 1;
            }else if(target < A[start]){
                return start;
            }else{
                return end;
            }
        }
       
        if(A[median] < target){
            return findBST(A, median + 1, end, target);
        }else{
            return findBST(A, start, median - 1, target);
        }
    }
}