public class Solution {

    public int searchInsert(int[] nums, int target) {
        return searchHelper(nums, target, 0, nums.length - 1);
    }

    public int searchHelper(int[] nums, int target, int start, int end){
        if(nums.length == 0){
            return 0;
        } else if (start == end){
            int element = nums[start];
            if(element == target){
                return start;
            } else if (element > target){
                return  start;
            } else {
                return start + 1;
            }
        } else {
            int returnVal;
            int offset = (end - start) / 2;
            int middle = start + offset; //middle index
            int middleNum = nums[middle]; //middle number
            if(target == middleNum){
                returnVal = middle;
            } else if(target > middleNum){
                returnVal = searchHelper(nums, target, Math.min(middle + 1, end), end);
            } else {
                returnVal = searchHelper(nums, target, start, Math.max(middle - 1, start));
            }
            return returnVal;
        }
    }
}