知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 05 - 搜索插入位置 ## 题目(LeetCode 35) 在有序数组中找 target,找到返回下标,找不到返回它应该插入的位置(保持数组有序)。 ``` 输入:nums = [1, 3, 5, 6], target = 5 输出:2(5 在下标 2) 输入:nums = [1, 3, 5, 6], target = 2 输出:1(2 应该插在下标 1,变成 [1, 2, 3, 5, 6]) 输入:nums = [1, 3, 5, 6], target = 7 输出:4(7 比所有数大,插在末尾) 输入:nums = [1, 3, 5, 6], target = 0 输出:0(0 比所有数小,插在开头) ``` ## 大白话理解 这道题本质就是:**找第一个 ≥ target 的位置**(lowerBound)。 如果 target 在数组中,lowerBound 就是它的下标;如果不在,lowerBound 就是它应该插入的位置。 想象你在一个按身高排好队的人群中,你要找到一个和你一样高的人的位置。如果没人跟你一样高,你就站在第一个比你高的人前面。 ## 代码 ```java public int searchInsert(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] == target) { return mid; // 找到了,直接返回 } else if (nums[mid] < target) { l = mid + 1; // 太小,去右边 } else { r = mid - 1; // 太大,去左边 } } // 没找到:此时 l 指向第一个 > target 的位置(也是应该插入的位置) // 同时也是第一个 >= target 的位置 return l; } ``` > 💬 **Q:为什么没找到时返回 `l` 就是答案?** > > 退出循环时 `l > r`,l 指向的是第一个 `>= target` 的位置。分情况验证: > > ``` > nums = [1, 3, 5, 6], target = 2 > 最终 l=1, r=0 → l=1,正是 2 应该插入的位置 ✓ > > nums = [1, 3, 5, 6], target = 7 > 最终 l=4, r=3 → l=4,正是 7 应该插入的位置(末尾)✓ > > nums = [1, 3, 5, 6], target = 0 > 最终 l=0, r=-1 → l=0,正是 0 应该插入的位置(开头)✓ > ``` ## 核心理解:`l` 指针的含义 ``` 在标准的 while(l <= r) 二分中: - l 不断右移,跳过所有 < target 的元素 - r 不断左移,跳过所有 > target 的元素 循环结束时: - l 指向第一个 >= target 的位置 - r 指向最后一个 < target 的位置 所以 l 就是插入位置! ``` ``` nums = [1, 3, 5, 6], target = 2 [1, 3, 5, 6] ↑ ↑ l r mid=1, nums[1]=3 > 2 → r=0 [1, 3, 5, 6] ↑ l,r mid=0, nums[0]=1 < 2 → l=1 [1, 3, 5, 6] ↑ l l=1, r=0 → l > r,退出 此时 l=1: 下标 1 之前都是 < 2 的元素([1]) 下标 1 及之后都是 >= 2 的元素([3, 5, 6]) → 2 应该插在下标 1 ✓ ``` ## 过程模拟 ### 场景1:target 在数组中 ``` nums = [1, 3, 5, 6], target = 5 第1轮: l=0, r=3, mid=1 → nums[1]=3 < 5 → l=2 第2轮: l=2, r=3, mid=2 → nums[2]=5 == 5 → 返回 2 ✓ ``` ### 场景2:target 不在数组中(插中间) ``` nums = [1, 3, 5, 6], target = 2 第1轮: l=0, r=3, mid=1 → nums[1]=3 > 2 → r=0 [1, 3, 5, 6] l r 第2轮: l=0, r=0, mid=0 → nums[0]=1 < 2 → l=1 [1, 3, 5, 6] l 第3轮: l=1, r=0 → l > r 退出 return l = 1 → 插入位置 = 1 ✓ → [1, 2, 3, 5, 6] ``` ### 场景3:target 比所有数大 ``` nums = [1, 3, 5, 6], target = 7 第1轮: l=0, r=3, mid=1 → nums[1]=3 < 7 → l=2 第2轮: l=2, r=3, mid=2 → nums[2]=5 < 7 → l=3 第3轮: l=3, r=3, mid=3 → nums[3]=6 < 7 → l=4 第4轮: l=4, r=3 → l > r 退出 return l = 4 → 插入位置 = 4(末尾)✓ → [1, 3, 5, 6, 7] ``` ### 场景4:target 比所有数小 ``` nums = [1, 3, 5, 6], target = 0 第1轮: l=0, r=3, mid=1 → nums[1]=3 > 0 → r=0 第2轮: l=0, r=0, mid=0 → nums[0]=1 > 0 → r=-1 第3轮: l=0, r=-1 → l > r 退出 return l = 0 → 插入位置 = 0(开头)✓ → [0, 1, 3, 5, 6] ``` ## 复杂度 - 时间:O(log n) - 空间:O(1) ## 一句话总结 标准二分找 target,找到返回,找不到返回 `l`。`l` 在退出时指向第一个 ≥ target 的位置,正好是插入位置。 --- 上一篇:[04 - 在排序数组中查找第一个和最后一个位置](./04-first-and-last.md) | 下一篇:[06 - 寻找峰值](./06-peak-element.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入