35.搜索插入位置-leetcode自解

思路：查找第一个target （题目说数组不重复）或者查找第一个大于target 的就可以了。

class Solution {
    public int searchInsert(int[] nums, int target) {
       int maxInNums = Arrays.stream(nums).max().getAsInt();
        if (target > maxInNums) {
            return nums.length;
        }
        return  findFirstTarget(nums, target);
    }
    public static int findFirstTarget(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;

        while(left < right) {
            int middle = (left + right) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        if (nums[left] == target) {
            return left;
        } else {
            int firstTarget = findFirstTarget(nums, target + 1);
            return firstTarget;
        }
    }
}