🌕 35. 搜索插入位置

难度: 🌕

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 思路：
        // 无重复元素升序
        // 有则返回下标，无则返回下标，该下标处 num > target 但是最接近 target
        int len = nums.length;
        // 特殊情况特判
        if(target <= nums[0]) {
            return 0;
        } 
        if(target > nums[len - 1]) {
            return len;
        }
        return mySol(nums, target, 0, len - 1);
    }

    private int mySol(int[] nums, int target, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return left;
        }
        // left < right
        int mid = left + ((right - left) >> 1);
        if(target == nums[mid]) {
            return mid;
        } else if(target < nums[mid]) {
            right = mid;
            return mySol(nums, target, left, right);
        } else {
            // target > nums[mid]
            left = mid + 1;
            return mySol(nums, target, left, right);
        }
    }
}

---

输出