二分查找基础原理与题目说明文章目录二分查找基础原理与题目说明一、 什么是二分查找二、 经典二分查找应用[35. 搜索插入位置](https://leetcode.cn/problems/search-insert-position/)[34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)三、 二维矩阵中的二分查找[74. 搜索二维矩阵](https://leetcode.cn/problems/search-a-2d-matrix/)[240. 搜索二维矩阵 II](https://leetcode.cn/problems/search-a-2d-matrix-ii/)四、 旋转排序数组系列[33. 搜索旋转排序数组](https://leetcode.cn/problems/search-in-rotated-sorted-array/)[153. 寻找旋转排序数组中的最小值](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/) 查看完整专栏LeetCode基础算法专栏点击阅读Python 数据结构与语法速查笔记点击阅读哈希表基础原理与题目说明点击阅读双指针基础原理与题目说明点击阅读滑动窗口基础原理与题目说明点击阅读队列与单调队列基础原理与题目说明点击阅读二分查找基础原理与题目说明点击阅读矩阵基础原理与题目说明特别说明本文为个人的 LeetCode 刷题与学习笔记内容仅供学习与交流使用禁止转载或用于商业用途。需要强调的是文中的题目解法不一定是最优解可能存在时间或空间复杂度的进一步优化空间主要目的是分享个人的解题思路与逻辑实现仅供参考。笔记内容为个人理解与总结可能存在疏漏或偏差欢迎读者自行甄别并交流探讨。一、 什么是二分查找二分查找Binary Search是基于分治减治思想的高效查找算法。针对有序区间通过「每轮排除一半搜索空间」的方式将查找效率从线性查找的O ( n ) O(n)O(n)飞跃提升到O ( log ⁡ n ) O(\log n)O(logn)。核心前提数据有序或具有某种可以明确切分的局部有序性/单调性。支持随机访问底层必须是数组链表等无法直接通过索引访问的结构不适用。二、 经典二分查找应用35. 搜索插入位置题目描述给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。要求O ( log ⁡ n ) O(\log n)O(logn)的时间复杂度。解题思路标准的**「找最左侧答案 / 插入位置」**模板题。初始化左闭右开区间[0, len(nums))这样能完美覆盖 target 大于所有元素需要插入到数组末尾的情况。每次判断nums[mid] target若是则left mid 1否则right mid最终left就是插入位置。核心代码fromtypingimportListclassSolution:defsearchInsert(self,nums:List[int],target:int)-int:left0rightlen(nums)# 左闭右开区间whileleftright:mid(leftright)//2ifnums[mid]target:returnmidelifnums[mid]target:leftmid1# 目标在右侧跳过 midelse:rightmid# 目标在左侧保留 mid 作为候选插入点# 循环结束时 left rightreturnleft34. 在排序数组中查找元素的第一个和最后一个位置题目描述给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果不存在返回[-1, -1]。解题思路这道题是左/右边界模板的完美结合第一次二分找第一个≥ t a r g e t \ge target≥target的位置左边界直接套用「找最左侧」模板。第二次二分找最后一个≤ t a r g e t \le target≤target的位置右边界直接套用「找最右侧」模板。最后通过验证边界的合法性与元素匹配性判断目标值是否存在。核心代码fromtypingimportListclassSolution:defsearchRange(self,nums:List[int],target:int)-List[int]:ifnotnums:return[-1,-1]# 1. 找第一个 target 的数值 —— 锁定最左边界left0rightlen(nums)whileleftright:mid(leftright)//2ifnums[mid]target:leftmid1else:rightmid start_idxleft# 2. 找最后一个 target 的数值 —— 锁定最右边界left0rightlen(nums)-1whileleftright:mid(leftright1)//2# 必须 1 防死循环ifnums[mid]target:rightmid-1else:leftmid end_idxleft# 3. 校验最终找到的区间是否合法且匹配 targetifstart_idxend_idxorstart_idxlen(nums)ornums[end_idx]!target:return[-1,-1]return[start_idx,end_idx]三、 二维矩阵中的二分查找74. 搜索二维矩阵题目描述给你一个m × n m \times nm×n整数矩阵。每行从左到右递增且每行的第一个整数大于前一行的最后一个整数。判断目标值是否存在于矩阵中。解题思路选用两次二分查找解题充分利用矩阵特性。第一次二分定位 target 可能所在的行。本质是找最后一个行首≤ t a r g e t \le target≤target的行这属于「找最右侧答案」套用对应模板。第二次二分在目标行内判断目标值是否存在这属于普通的二分查找判定。整体时间复杂度O ( log ⁡ ( m ) log ⁡ ( n ) ) O ( log ⁡ ( m n ) ) O(\log(m) \log(n)) O(\log(mn))O(log(m)log(n))O(log(mn))。核心代码fromtypingimportListclassSolution:defsearchMatrix(self,matrix:List[List[int]],target:int)-bool:# 1. 第一次二分定位 target 所在的行left0rightlen(matrix)-1whileleftright:mid(leftright1)//2# 找最右侧满足条件的行加1防死循环ifmatrix[mid][0]target:rightmid-1else:leftmid rowleft# 锁定目标行# 2. 第二次二分在目标行中查找 targetleft0rightlen(matrix[0])-1# 此处采用精确匹配的闭区间写法whileleftright:mid(leftright)//2ifmatrix[row][mid]target:returnTrueelifmatrix[row][mid]target:leftmid1else:rightmid-1returnFalse240. 搜索二维矩阵 II题目描述矩阵每行从左到右升序每列从上到下升序。搜索目标值。解题思路注本题有从右上角出发O ( m n ) O(mn)O(mn)的解法此处分享基于二分思想的解法。逐行遍历由于每一行都是严格升序的可以直接对每一行套用标准的「左闭右闭」一维二分模板。虽然不是最优的时间复杂度但逻辑清晰、健壮。核心代码fromtypingimportListclassSolution:defsearchMatrix(self,matrix:List[List[int]],target:int)-bool:ifnotmatrixornotmatrix[0]:returnFalsen,mlen(matrix),len(matrix[0])foriinrange(n):left,right0,m-1whileleftright:mid(leftright)//2ifmatrix[i][mid]target:returnTrueelifmatrix[i][mid]target:leftmid1else:rightmid-1returnFalse四、 旋转排序数组系列旋转数组打破了全局的有序性但保留了局部有序性。二分的难点在于如何通过mid判断目标值落在左半段还是右半段。33. 搜索旋转排序数组题目描述整数数组nums按升序排列且互不相同在某个下标上进行了旋转。求目标值target的下标。要求O ( log ⁡ n ) O(\log n)O(logn)复杂度。解题思路原数组旋转后通过mid切开必定有一半区间是严格升序的。判断哪一半有序通过判断nums[left] nums[mid]若成立说明[left, mid]有序否则[mid, right]有序。判断 target 是否在有序区间内如果在有序的那一半区间内直接将边界收缩到该区间如果不在则说明在另一半乱序区间内收缩到另一半。核心代码fromtypingimportListclassSolution:defsearch(self,nums:List[int],target:int)-int:left0rightlen(nums)-1whileleftright:mid(leftright)//2ifnums[mid]target:returnmid# 1. 左半区间 [left, mid] 是严格有序的ifnums[left]nums[mid]:# 检查 target 是否在有序的左半区间内ifnums[left]targetnums[mid]:rightmid-1else:leftmid1# 2. 否则右半区间 [mid, right] 是严格有序的else:# 检查 target 是否在有序的右半区间内ifnums[mid]targetnums[right]:leftmid1else:rightmid-1return-1153. 寻找旋转排序数组中的最小值题目描述找出并返回旋转后升序数组中的最小元素。要求O ( log ⁡ n ) O(\log n)O(logn)。解题思路旋转后数组被分为两段连续的升序子数组且前一段的所有元素必定大于后一段的所有元素。最小值就是这两段的分界点。我们将nums[mid]与右边界nums[right]进行比较若nums[mid] nums[right]说明右侧是严格递增的最小值一定在左侧或就是mid故right mid。若nums[mid] nums[right]说明出现了断层最小值一定在mid右侧故left mid 1。核心代码fromtypingimportListclassSolution:deffindMin(self,nums:List[int])-int:left0rightlen(nums)-1whileleftright:mid(leftright)//2# 若 mid 小于最右侧元素说明 mid 到 right 是递增的# 最小值必然在 left 到 mid 之间ifnums[mid]nums[right]:rightmid# 若 mid 大于最右侧说明断层在右边else:leftmid1returnnums[left]