【二分查找的右边界】LCR 068. 搜索插入位置

LCR 068. 搜索插入位置

解题思路

• 二分查找的右边界
• 如果找到直接返回
• 如果没找到那么返回右边界的下一个位置

class Solution {
    public int searchInsert(int[] nums, int target) {

        int right = right_bound(nums,target);



        return right;
    }

    int right_bound(int[] nums,int target){
        // 寻找左边界

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

        while(left <= right){
            int mid = (right - left) / 2 + left;

            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid  - 1;
            }else if(nums[mid] == target){
                right = mid - 1;
            }
        }

        // 没找到 那么直接插入右边界的下一个位置
        if(right < 0 || nums[right] != target){
            return right + 1;
        }

        return right;
    }
}