LeetCode 35 搜索插入位置——二分查找入门必刷题

LeetCode 35 搜索插入位置——二分查找入门必刷题

前言

二分查找可以说是算法面试中的高频考点，也是很多复杂算法的基础。

很多同学第一次学习二分查找时，总是被各种边界条件绕晕：

• 为什么是left <= right？
• 为什么更新边界时要mid + 1和mid - 1？
• 为什么最后返回的是left？
• 为什么时间复杂度是 O(logn)？

而 LeetCode 35《搜索插入位置》正是学习二分查找最经典的入门题。

一、题目描述

给定一个升序排列的整数数组 nums 和一个目标值 target。

如果目标值存在于数组中，返回其下标；

如果不存在，则返回它应该插入的位置。

要求时间复杂度为 O(log n)。

示例：

nums=[1,3,5,6]target=5输出：2

nums=[1,3,5,6]target=2输出：1

nums=[1,3,5,6]target=7输出：4

二、为什么想到二分查找？

题目有一个非常关键的信息：

数组已经升序排列

只要看到：

• 有序数组
• 查找元素
• O(logn)

基本就要想到二分查找。

因为普通遍历需要：

O(n)

而二分查找每次都能排除一半区间：

O(logn)

效率提升非常明显。

三、核心思想

假设：

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

第一次取中间：

mid=1nums[mid]=3

发现：

2<3

说明目标一定在左半部分。

因此直接舍弃右半部分：

right=mid-1

搜索区间缩小一半。

不断重复这个过程即可。

四、标准模板

classSolution:defsearchInsert(self,nums,target):left=0right=len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1returnleft

五、为什么最后返回 left？

这是本题最重要的知识点。

假设：

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

执行过程：

left=0right=3

第一次：

mid=1nums[mid]=3

因为：

2<3

所以：

right=0

第二次：

mid=0nums[mid]=1

因为：

2>1

所以：

left=1

此时：

left=1right=0

循环结束。

最终：

left=1

正好就是数字2应该插入的位置。

因此：

returnleft

六、二分查找本质

这道题其实是在找：

第一个大于等于 target 的位置

例如：

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

第一个大于等于4的元素是：

5

对应下标：

2

这就是答案。

很多高级二分题本质上也都是寻找：

• 第一个大于等于x
• 第一个大于x
• 最后一个小于等于x
• 最后一个小于x

因此这道题非常值得掌握。

七、高频易错点

1. mid计算错误

错误：

mid=(left+right)/2

得到浮点数。

正确：

mid=(left+right)//2

2. 循环条件写错

左闭右闭区间：

whileleft<=right

不能写成：

whileleft<right

否则最后一个元素可能漏掉。

3. 边界更新方向写反

目标更小：

right=mid-1

目标更大：

left=mid+1

不要写反。

4. right初始化错误

正确：

right=len(nums)-1

因为最后一个元素下标是：

len(nums)-1

八、总结

本题是二分查找最经典的模板题。

核心记住三点：

1. 有序数组 + O(logn) → 二分查找
2. 左闭右闭区间使用left <= right
3. 没找到时返回left

掌握本题之后，可以继续练习：

• LeetCode 704 二分查找
• LeetCode 34 在排序数组中查找元素的第一个和最后一个位置
• LeetCode 69 x的平方根
• LeetCode 278 第一个错误的版本

这些题目本质都建立在同一个二分模板之上。