LeetCode 35 搜索插入位置——二分查找入门必刷题前言二分查找可以说是算法面试中的高频考点也是很多复杂算法的基础。很多同学第一次学习二分查找时总是被各种边界条件绕晕为什么是left right为什么更新边界时要mid 1和mid - 1为什么最后返回的是left为什么时间复杂度是 O(logn)而 LeetCode 35《搜索插入位置》正是学习二分查找最经典的入门题。一、题目描述给定一个升序排列的整数数组 nums 和一个目标值 target。如果目标值存在于数组中返回其下标如果不存在则返回它应该插入的位置。要求时间复杂度为 O(log n)。示例nums[1,3,5,6]target5输出2nums[1,3,5,6]target2输出1nums[1,3,5,6]target7输出4二、为什么想到二分查找题目有一个非常关键的信息数组已经升序排列只要看到有序数组查找元素O(logn)基本就要想到二分查找。因为普通遍历需要O(n)而二分查找每次都能排除一半区间O(logn)效率提升非常明显。三、核心思想假设nums[1,3,5,6]target2第一次取中间mid1nums[mid]3发现23说明目标一定在左半部分。因此直接舍弃右半部分rightmid-1搜索区间缩小一半。不断重复这个过程即可。四、标准模板classSolution:defsearchInsert(self,nums,target):left0rightlen(nums)-1whileleftright:mid(leftright)//2ifnums[mid]target:returnmidelifnums[mid]target:leftmid1else:rightmid-1returnleft五、为什么最后返回 left这是本题最重要的知识点。假设nums[1,3,5,6]target2执行过程left0right3第一次mid1nums[mid]3因为23所以right0第二次mid0nums[mid]1因为21所以left1此时left1right0循环结束。最终left1正好就是数字2应该插入的位置。因此returnleft六、二分查找本质这道题其实是在找第一个大于等于 target 的位置例如nums[1,3,5,6]target4第一个大于等于4的元素是5对应下标2这就是答案。很多高级二分题本质上也都是寻找第一个大于等于x第一个大于x最后一个小于等于x最后一个小于x因此这道题非常值得掌握。七、高频易错点1. mid计算错误错误mid(leftright)/2得到浮点数。正确mid(leftright)//22. 循环条件写错左闭右闭区间whileleftright不能写成whileleftright否则最后一个元素可能漏掉。3. 边界更新方向写反目标更小rightmid-1目标更大leftmid1不要写反。4. right初始化错误正确rightlen(nums)-1因为最后一个元素下标是len(nums)-1八、总结本题是二分查找最经典的模板题。核心记住三点有序数组 O(logn) → 二分查找左闭右闭区间使用left right没找到时返回left掌握本题之后可以继续练习LeetCode 704 二分查找LeetCode 34 在排序数组中查找元素的第一个和最后一个位置LeetCode 69 x的平方根LeetCode 278 第一个错误的版本这些题目本质都建立在同一个二分模板之上。