35. 搜索插入位置

📝 题目描述

给定一个无重复元素的升序排列数组 nums 和一个目标值 target，在数组中找到目标值并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 要求：必须使用时间复杂度为 O(log n) 的算法。

---

📌 示例

示例 1

输入：

nums = [1,3,5,6], target = 5

输出：

2

解释：target=5 存在于数组中，索引为 2。

示例 2

输入：

nums = [1,3,5,6], target = 2

输出：

1

解释：target=2 不存在，按顺序应插入到 1 和 3 之间，位置为 1。

示例 3

输入：

nums = [1,3,5,6], target = 7

输出：

4

解释：target=7 比数组所有元素都大，应插入到末尾，位置为 4。

---

🚀 最优解：二分查找定位（找“第一个≥target”的位置）

🔍 思路解析

核心策略：用二分查找找“第一个大于等于target的元素位置”，这个位置就是target的插入点（存在则是自身索引）。

1. 初始化二分边界：left=0，right=nums.length-1；
2. 每次取中间索引 mid，比较 nums[mid] 与 target：
   • 若 nums[mid] < target：说明target在右侧，更新 left=mid+1；
   • 若 nums[mid] > target：说明target在左侧，更新 right=mid-1；
   • 若 nums[mid] == target：直接返回 mid（找到目标）；
3. 循环结束后，left 的值就是“第一个≥target”的位置（即插入点），返回 left。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 读取目标值
        int target = scanner.nextInt();

        // 创建解决方案对象并计算结果
        Solution solution = new Solution();
        int result = solution.searchInsert(nums, target);

        // 输出结果
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 避免溢出
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid; // 找到目标，返回索引
            }
        }
        // 循环结束时，left是第一个≥target的位置
        return left;
    }
}

---

🧠 通俗易懂解释

可以把数组想象成“排好队的数”，我们要找target该站的位置：

• 如果target在队伍里，直接站回自己的位置；
• 如果不在，就站到“第一个比自己大的数”前面。

以示例2 nums=[1,3,5,6], target=2 为例：

1. 初始left=0，right=3，mid=1 → nums[1]=3>2，所以right=0；
2. 新mid=0 → nums[0]=1<2，所以left=1；
3. 循环结束，left=1 → 这就是2该插入的位置。

---

⏱ 时间复杂度

O(log n)

二分查找的时间复杂度为对数级别，符合题目要求。

---

💾 空间复杂度

O(1)

仅使用left、right、mid等常数个变量，无额外空间消耗。

---