当前位置:网站首页>二分查找(折半查找)
二分查找(折半查找)
2022-07-05 06:50:00 【rockvine】
一、算法解释
二分查找也常被称为二分法或者折半查找,每次查找时通过将待查找区间分成两部分并只取一部分继续查找,将查找的复杂度大大减少。对于一个长度为 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(x),若 f(a) 和 f(b) 正负性相反,那么必定存在一个解 c,使得f(c) = 0。在上个例子中,f(x) 是离散函数 f(x) = x + 2,查找 4 是否存在等价于求 f(x) - 4 = 0 是否有离散解。因为 f(1) - 4 = 3 - 4 = -1 < 0,f(5) - 4 = 7 - 4 = 3 > 0,且函数在区间内单调递增,因此我们可以利用二分查找求解。如果最后二分到了不能再分的情况,如只剩一个数字,且剩余区间里不存在满足条件的解,则说明不存在离散解,即 4 不在这个数组内。
具体到代码上,二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以,因此有时会容易搞不清楚如何定义区间开闭性。这里提供两个小诀窍,第一是尝试熟练使用一种写法,比如左闭右开(满足编程的习惯)或左闭右闭(便于处理边界条件), 尽量只保持这一种写法;第二是在刷题时思考如果最后区间只剩下一个数或者两个数,自己的写法是否会陷入死循环,如果某种写法无法跳出死循环,则考虑尝试另一种写法。
二分查找也可以看作双指针的一种特殊情况,但我们一般会将二者区分。双指针类型的题, 指针通常是一步一步移动的,而在二分查找里,指针每次移动半个区间长度。
二、求开方
2.1、x 的平方根
2.1.1、题目描述
69. x 的平方根
给你一个非负整数x
,计算并返回x
的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意: 不允许使用任何内置指数函数和算符,例如pow(x, 0.5)
或者x ** 0.5
。
2.1.2、输入输出示例
示例1:
输入: x = 4
输出: 2
示例2:
输入: x = 8
输出: 2
解释: 8 的算术平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。
2.1.3、题解
二分查找的下界为 0,上界可以粗略地设定为 x。在二分查找的每一步中,我们只需要比较中间元素 mid 的平方与 x 的大小关系,并通过比较的结果调整上下界的范围。
class Solution {
public int mySqrt(int x) {
int left = 0, right = x, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if ((long) mid * mid <= x) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
}
复杂度分析
- 时间复杂度:O(logx),即为二分查找需要的次数。
- 空间复杂度:O(1)。
三、查找区间
3.1、在排序数组中查找元素的第一个和最后一个位置
3.1.1、题目描述
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组nums
,和一个目标值target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值target
,返回[-1, -1]
。
你必须设计并实现时间复杂度为O(log n)
的算法解决此问题。
3.1.2、输入输出示例
示例1:
输入: nums = [5, 7, 7, 8, 8, 10], target = 8
输出: [3,4]
示例2:
输入: nums = [5, 7, 7, 8, 8, 10], target = 6
输出: [-1,-1]
示例3:
输入: nums = [], target = 0
输出: [-1,-1]
3.1.3、题解
四、选择数组查找数字
4.1、搜索旋转排序数组 II
4.1.1、题目描述
81. 搜索旋转排序数组 II
已知存在一个按非降序排列的整数数组nums
,数组中的值不必互不相同。
在传递给函数之前,nums
在预先未知的某个下标k
(0 <= k < nums.length
)上进行了 旋转 ,使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如,[0,1,2,4,4,4,5,6,6,7]
在下标 5 处经旋转后可能变为[4,5,6,6,7,0,1,2,4,4]
。
给你 旋转后 的数组nums
和一个整数target
,请你编写一个函数来判断给定的目标值是否存在于数组中。如果nums
中存在这个目标值target
,则返回true
,否则返回false
。
你必须尽可能减少整个操作步骤。
4.1.2、输入输出示例
示例1:
输入: nums = [2, 5, 6, 0, 0, 1, 2], target = 0
输出: true
示例2:
输入: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
输出: false
4.1.3、题解
五、练习
5.1、基础难度
5.1.1、寻找旋转排序数组中的最小值 II
5.1.1.1、题目描述
寻找旋转排序数组中的最小值 II
已知一个长度为n
的数组,预先按照升序排列,经由1
到n
次 旋转 后,得到输入数组。例如,原数组nums = [0,1,4,4,5,6,7]
在变化后可能得到:
- 若旋转 4 次,则可以得到 [4,5,6,7,0,1,4]
- 若旋转 7 次,则可以得到 [0,1,4,4,5,6,7]
注意,数组
[a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。
给你一个可能存在 重复 元素值的数组nums
,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。
5.1.1.2、输入输出示例
示例1:
输入: nums = [1, 3, 5]
输出: 1
示例1:
输入: nums = [2, 2, 2, 0, 1]
输出: 0
5.1.1.3、题解
5.1.2、有序数组中的单一元素
5.1.2.1、题目描述
有序数组中的单一元素
给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足O(log n)
时间复杂度和O(1)
空间复杂度。
5.1.2.2、输入输出示例
示例1:
输入: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
输出: 2
示例1:
输入: nums = [3, 3, 7, 7, 10, 11, 11]
输出: 10
5.1.2.3、题解
5.2、进阶难度
5.2.1、寻找两个正序数组的中位数
5.2.1.1、题目描述
寻找两个正序数组的中位数
给定两个大小分别为m
和n
的正序(从小到大)数组nums1
和nums2
。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为O(log (m+n))
。
5.2.1.2、输入输出示例
示例1:
输入: nums1 = [1, 3], nums2 = [2]
输出: 2.00000
解释: 合并数组 = [1, 2, 3] ,中位数 2
示例1:
输入: nums1 = [1, 2], nums2 = [3, 4]
输出: 2.50000
解释: 合并数组 = [1, 2, 3, 4] ,中位数 (2 + 3) / 2 = 2.5
5.2.1.3、题解
边栏推荐
- SD_CMD_RECEIVE_SHIFT_REGISTER
- PHY驱动调试之 --- MDIO/MDC接口22号和45号条款(一)
- Log4qt usage of logbase in QT project
- 【MySQL8.0不支持表名大写-对应方案】
- A brief introduction to heading/pitch/roll and omega/phi/kappa
- UIO driven framework
- Mutual transformation between two-dimensional array and sparse array (sparse matrix)
- ROS2——工作空间(五)
- 解读最早的草图-图像翻译工作SketchyGAN
- 基于Cortex-M3、M4的GPIO口位带操作宏定义(可总线输入输出,可用于STM32、ADuCM4050等)
猜你喜欢
GDB code debugging
达梦数据库全部
Skywalking全部
LSA Type Explanation - lsa-1 [type 1 LSA - router LSA] detailed explanation
Ros2 - workspace (V)
Orin two brushing methods
Ret2xx---- common CTF template proposition in PWN
Use the Paping tool to detect TCP port connectivity
SD_CMD_RECEIVE_SHIFT_REGISTER
Marvell 88e1515 PHY loopback mode test
随机推荐
Ros2 - node (VII)
How to answer when you encounter a jet on CSDN?
The “mode“ argument must be integer. Received an instance of Object
SOC_SD_DATA_FSM
The route of wechat applet jumps again without triggering onload
Record of problems in ollvm compilation
The problem of Chinese garbled code in the vscode output box can be solved once for life
Skywalking全部
postmessage通信
ROS2——功能包(六)
你心目中的数据分析 Top 1 选 Pandas 还是选 SQL?
全局变量和静态变量的初始化
Orin installs CUDA environment
Sum of two numbers, the numbers in the array are converted to decimal, added, and output inversely
微信小程序路由再次跳轉不觸發onload
ethtool 原理介绍和解决网卡丢包排查思路(附ethtool源码下载)
Marvell 88E1515 PHY loopback模式测试
Error: “MountVolume.SetUp failed for volume pvc 故障处理
并发编程 — 如何中断/停止一个运行中的线程?
LSA Type Explanation - lsa-5 (type 5 LSA - autonomous system external LSA) and lsa-4 (type 4 LSA - ASBR summary LSA) explanation