type
status
date
slug
summary
tags
category
icon
password
网址
📝 算法解释
二分查找也常被称为二分法或者折半查找 (binary search, bisect),每次查找时通过将待查找的单调区间分成两部分并只取一部分继续查找,将查找的复杂度大大减少。对于一个长度为 O(n)的数组,二分查找的时间复杂度为 O(log n)。
举例来说,给定一个排好序的数组 {3,4,5,6,7},我们希望查找 4 在不在这个数组内。第一次折半时考虑中位数 5,因为 5 大于 4, 所以如果 4 存在于这个数组,那么其必定存在于 5 左边这一半。于是我们的查找区间变成了 {3,4,5}。(注意,根据具体情况和您的刷题习惯,这里的 5 可以保留也可以不保留,并不影响时间复杂度的级别。)第二次折半时考虑新的中位数 4,正好是我们需要查找的数字。于是我们发现,对于一个长度为 5 的数组,我们只进行了 2 次查找。如果是遍历数组,最坏的情况则需要查找 5 次。
我们也可以用更加数学的方式定义二分查找。给定一个在 [a,b] 区间内的单调函数 f (t),若f (a) 和 f (b) 正负性相反,那么必定存在一个解 c,使得 f (c) = 0。在上个例子中,f (t) 是离散函数f (t) = t + 2,查找 4 是否存在等价于求 f (t) − 4 = 0 是否有离散解。因为 f (1) − 4 = 3 − 4 = −1 < 0、f (5) − 4 = 7 − 4 = 3 > 0,且函数在区间内单调递增,因此我们可以利用二分查找求解。如果最后二分到了不能再分的情况,如只剩一个数字,且剩余区间里不存在满足条件的解,则说明不存在离散解,即 4 不在这个数组内。
具体到代码上,二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以,因此有些初学者会容易搞不清楚如何定义区间开闭性。这里笔者提供两个小诀窍,第一是尝试熟练使用一种写法,比如左闭右开(满足 C++、Python 等语言的习惯)或左闭右闭(便于处理边界条件),尽量只保持这一种写法;第二是在刷题时思考如果最后区间只剩下一个数或者两个数,自己的写法是否会陷入死循环,如果某种写法无法跳出死循环,则考虑尝试另一种写法。
二分查找也可以看作双指针的一种特殊情况,但我们一般会将二者区分。双指针类型的题,指针通常是一步一步移动的,而在二分查找里,指针通常每次移动半个区间长度。
求开方
69. x 的平方根
题目描述
给定一个非负整数 x,求它的开方,向下取整。
输入输出样例
输入一个整数,输出一个整数。
8的开方结果是 2.82842...,向下取整即是 2。
题解
我们可以把这道题想象成,给定一个非负整数 x,求 f (t) = t^2 − x = 0 的解。因为我们只考虑 t ≥ 0,所以 f (t) 在定义域上是单调递增的。考虑到 f (0) = −x ≤ 0, f (x) = x^2 − x ≥ 0,我们可以对 [0, x] 区间使用二分法找到 f (t) = 0 的解。这里笔者使用了左闭右闭的写法。
查找区间
34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
给定一个增序的整数数组和一个值,查找该值第一次和最后一次出现的位置。
输入输出样例
输入是一个数组和一个值,输出为该值第一次出现的位置和最后一次出现的位置(从 0 开始);如果不存在该值,则两个返回值都设为-1。
数字 8 在第 3 位第一次出现,在第 4 位最后一次出现。
题解
这道题可以看作是自己实现 C++ 里的 lower_bound 和 upper_bound 函数,或者 Python 里的 bisect_left 和 bisect_right 函数。这里我们尝试使用左闭右开的写法,当然左闭右闭也可以。
查找峰值
162. 寻找峰值
题目描述
给定一个数组,定义峰值为比所有两边都大的数字,求峰值的位置。一个数组里可能存在多个峰值,返回任意一个即可。时间复杂度要求为 O(log n)。
输入输出样例
输入是一个数组,输出为峰值的位置。
峰值 3 出现在位置 2
题解
要实现 O(log n) 时间复杂度,我们可以对数组进行二分查找。在确保两端不是峰值后,若当前中点不是峰值,那么其左右一侧一定有一个峰值。
旋转数组查找数字
81. 搜索旋转排序数组 II
题目描述
一个原本增序的数组被首尾相连后按某个位置断开(如 [1,2,2,3,4,5] → [2,3,4,5,1,2],在第一位和第二位断开),我们称其为旋转数组。给定一个值,判断这个值是否存在于这个旋转数组中。
输入输出样例
输入是一个数组和一个值,输出是一个布尔值,表示数组中是否存在该值。
题解
即使数组被旋转过,我们仍然可以利用这个数组的递增性,使用二分查找。对于当前的中点,如果它指向的值小于等于右端,那么说明右区间是排好序的;反之,那么说明左区间是排好序的。如果目标值位于排好序的区间内,我们可以对这个区间继续二分查找;反之,我们对于另一半区间继续二分查找。本题我们采用左闭右闭的写法。
🤗 练习
基础难度
154. 寻找旋转排序数组中的最小值 II
旋转数组的变形题之一。
题目解析
这个题目(LeetCode 154: 寻找旋转排序数组中的最小值 II)是“旋转排序数组”系列的进阶版(之前你做过搜索变体)。核心挑战是:
- 输入:一个长度为 n 的数组 nums,原本是升序排列(非降序,可能有重复),经过 1~n 次旋转后得到当前形式。旋转定义:每次把最后一个元素移到开头(右移)。
- 输出:返回数组中的最小元素。
- 约束:
- 数组可能有重复元素(如 [2,2,2,0,1])。
- 时间复杂度:尽可能 O(log n),但由于重复,最坏 O(n)。
- 空间:O(1)。
- 关键性质:
- 旋转后,数组分成两段:从旋转点到末尾(降序部分),和从头到旋转点(升序部分)。最小值在“拐点”处(旋转点后第一个元素)。
- 无旋转时,整个数组升序,最小是 nums[0]。
- 有重复:无法简单比较 mid 和 0 来判断拐点。
示例:
- [1,3,5]:无旋转或全旋转,最小 1。
- [2,2,2,0,1]:旋转后,最小 0(在索引 3)。
直观:线性扫描 O(n) 太慢,用二分找“拐点”。
解题思路
利用二分搜索找最小值(拐点)。核心:比较 nums[mid] 和 nums[r] 来判断最小在哪半。
- 初始化:l = 0, r = n-1。
- 循环 while l < r:
- mid = (l + r) // 2
- 情况1:nums[mid] > nums[r] → 右半有更小(包括 r),最小在 mid+1 ~ r → l = mid + 1
- 情况2:nums[mid] < nums[r] → 右半升序,最小在左半或 mid → r = mid(包含 mid)
- 情况3:nums[mid] == nums[r] → 重复,无法判断哪半有序,但 r 不是最小(因为等于 mid ≥ 最小),安全缩小:r -= 1
- 结束:nums[l] 就是最小(l == r 时)。
为什么有效?
- 情况1/2:标准旋转判断,缩小一半。
- 情况3:重复时“牺牲”一步(O(n) 最坏,如全 2 的数组),但平均仍 log n。
- 无重复时退化为 153 题(找最小)。
540. 有序数组中的单一元素
在出现独立数之前和之后,奇偶位数的值发生了什么变化?
解题思路
利用配对性质:在有序数组中,两次出现的元素总是成对出现(相邻且相等)。单一元素会“打破”这种对称性。
- 二分搜索的核心:每次检查中点 mid 附近是否“配对正常”。
- 用索引的奇偶性来判断预期配对位置(因为 0-based 索引,从 0 开始是偶数)。
- 如果 mid 是偶数:预期 nums[mid] == nums[mid+1](成对在 mid 和 mid+1)。
- 如果相等 → 左半边(包括 mid)全配对,单一在右半边 → 跳到 mid + 2(跳过一对)。
- 如果不相等 → 单一在左半边(mid 或之前) → 搜索左半到 mid。
- 如果 mid 是奇数:预期 nums[mid] == nums[mid-1](成对在 mid-1 和 mid)。
- 如果相等 → 左半边全配对,单一在右半边 → 跳到 mid + 2。
- 如果不相等 → 单一在右半边(mid 或之后) → 搜索 mid 到右端。
- 边界:当 l == r 时,就是单一元素。
- 为什么 O(log n):每次缩小一半(或跳过一对),搜索空间 halving。
- 为什么 O(1) 空间:只用两个指针 l 和 r。
这个思路巧妙地“模拟”了寻找不配对的位置,就像找“奇数”在成对中的那个。
进阶难度
4. 寻找两个正序数组的中位数
需要对两个数组同时进行二分搜索。
题目解析
这个题目(LeetCode 4: 寻找两个正序数组的中位数)是二分搜索的经典应用,难度高主要是因为需要严格满足 O(log(m+n)) 时间(不能合并数组)。核心要求:
- 输入:两个升序(非降序)整数数组 nums1 (大小 m) 和 nums2 (大小 n)。
- 输出:合并后的中位数(浮点数)。
- 约束:
- 时间:O(log(min(m,n))),因为在较短数组上二分。
- 空间:O(1)。
- 数组可能空,但总长至少1(标准假设)。
- 中位数定义:
- 总元素 k = m + n。
- 如果 k 奇数:第 (k//2 + 1) 个元素(1-based)。
- 偶数:第 k//2 和 k//2 +1 个的平均。
- 示例:
- [1,3] + [2] → [1,2,3],中位 2。
- [1,2] + [3,4] → [1,2,3,4],中位 (2+3)/2 = 2.5。
直观:合并排序 O(m+n) 太慢,二分找“分割点”使左右半平衡。
解题思路
想象合并数组,但不用真合并:用二分找一个“分割线”,将两个数组分成左/右两部分,总左半元素 = total//2(或 +1 处理奇偶)。
- 假设:让 nums1 较短 (m <= n),否则交换。
- 二分目标:在 nums1 上找分割 i (0 <= i <= m),nums1[0..i) 是左半,nums1[i..m) 是右半。
- 则 nums2 的分割 j = (total//2) - i + (1 if 奇 else 0)? 精确:左半总需 k = (m+n+1)//2 个元素(用 +1 统一奇偶,奇时取左半最大,偶时平均)。
- j = k - i。
- 有效分割条件(左右平衡):
- 左半最大 <= 右半最小:max(nums1[i-1], nums2[j-1]) <= min(nums1[i], nums2[j])
- 简化:nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]
- 二分调整:
- 如果 nums1[i-1] > nums2[j]:i 太大(左半太大),缩小 i:r = mid - 1
- 否则:l = mid + 1
- 边界:
- i=0:nums1[i-1] 不存在,用 -inf
- i=m:nums1[i] 不存在,用 +inf
- 同理 j=0 或 j=n。
- 返回中位数:
- leftMax = max(nums1[i-1], nums2[j-1])
- rightMin = min(nums1[i], nums2[j])
- 如果 (m+n) 奇:leftMax
- 偶:(leftMax + rightMin) / 2.0
为什么 O(log(min(m,n)))?二分在短数组上,每次 halving。
- Author:无敌宝宝男sp
- URL:http://www.wudibaobaoda.top/article/2844032f-33bf-8047-8fc9-ed080d1976bd
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!