算法范式系列–二分算法
- 算法是Coder用来高效解决各种问题的屠龙刀,算法范式系列旨在武装自己的算法库。
- 这次来强化二分算法技能,二分算法可是个好东西,高效,好用,真香!!!
- 整理一些关于二分算法的想法以及刷题总结
一、关于二分算法
可以使用二分算法的条件
- 有序数列,(链表以及无序数组不行)
复杂度
- 时间复杂度:O(logN)
- 空间复杂度:迭代实现O(1),递归实现O(logN)
二分算法的思想
- 减治思想:不断缩小问题的规模
- 排除法:排除掉不满足的区间
什么时候该想到二分算法
- 在一个有序数组中进行查找
- 查找一个值,或者一个边界
- 半有序也可以,比如旋转、山脉数组
- 答案是二分的,即可以用排除法作为判断条件
- 查找一个有范围的整数
- 算法复杂度要求O(logN)
- 在一个有序数组中进行查找
二分查找循环体规定
[left, right]
, 双闭区间- 这个原则基本不变,之后的各种处理就比较统一了
二、二分算法解题思路
1. 能否用二分查找
- 是否有序or半有序
- 是否是查找一个有范围的整数
- 二分判断条件是什么,排除条件是什么
2. 选择二分范式
范式一:在区间中查找特定的值
- 区间分为左,中,右,三个部分
- 比较简单的二分查找
范式二:查找一个整数区间中的一个值或者边界情况
- 区间分为,已排除和未排除两个部分
- 适用于处理分界以及复杂问题
3. 使用范式编写代码
范式一
- 编写三个区间的判断,并对区间进行进一步缩小
- 终止条件,
left > right
范式二
- 编写排除条件
- 根据题意排除区间,mid不包括在新区间中
- 编写待排除区间
- 不用多虑,直接是上一个区间的反区间
- 检查mid的取值,向上取整还是向下
- 左区间为满足条件时,要向上取整
- 标志:else部分 left = middle
- 右区间为满足条件时,要向下取整
- 标志:else部分 right = middle
- 取整错误,区间缩小为2的时候,无法继续缩小下去了
- 左区间为满足条件时,要向上取整
- 检查查找结束后的left是否覆盖题意的范围
- 默认返回范围在,[left, right]中
- 有时候查找结果可能超出这个区间,比如right位置的下一个
- 两种解决
- 特别判断
- 在设置初始循环体时,将边界条件囊括其中。(推荐)
- 比如,right一般取len-1,但有时候,结果范围包括len时,right取len
三、二分查找的两个编程范式
- 二分可以通过迭代以及递归实现,推荐使用迭代实现。
- 这里仅提供迭代实现的两个范式,递归的能不用就不用。
- 避免mid溢出:
int mid = left + ( right - left) /2;
二分范式一
- 擅长查找特定的值,查找到了则直接返回结果。
- 其将区间分为 left,mid,right三个区间,分别对这三个区间进行判断。
- 终止条件:left > right, 即
while(left <= right)
- 终止后,left和right的取值情况不好确定
- 所以只擅长精准查找并返回,不擅长查找结束后的处理
- 如果需要查找边界等情况,推荐使用范式二
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16int binarySearchFor(int[] nums, int target) {
int result = -1;
int left = 0, right = nums.length - 1; // 闭区间
while (left <= right) { // left > right 终止
int mid = left +( right - left) / 2; // 避免mid溢出
if (nums[mid] == target) { // 三段条件判断
result = mid;
break;
} else if (nums[mid] < target) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return result;
}
二分范式二
- 擅长处理各种边界查找问题
- 原理思想:通过不断将不满足区间条件一边排除,不断缩小范围,最终left便为查找结果。
- 如果mid不在满足条件的区间,则将该区间包括mid,排除掉
- 如果mid在满足条件的区间,则再缩小区间时候,保留mid
- 需要抽取出区间选择条件,即大于等于,小于等于之类的
- 终止条件:left == right, 即
while(left < right)
- 查找终止后,left的位置是比较明确的,就是查找元素的边界位置
- 至于是之后取上边界还是下边界,再进一步判断
- mid 取整:
- 主要是第二个条件分支中的
left=mid
和right=mid
语句造成的- 目的是,当区间长度为2时,能进一步缩小区间。
- 当为
left=mid
,区间长度为2时,如果向下取整,则区间永远为2,死循环。 - 同理
right=mid
, 区间长度为2时,如果向上取整,则区间永远为2,死循环。
- 如果排除的是左区间,则向下取整
int mid = left + (right - left) / 2;
- 如果排除的是右区间,则向上取整
int mid = left + (right - left + 1) / 2;
- 主要是第二个条件分支中的
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28// 排除左区间
int binarySearchFor(int[] nums, int target) {
int left = 0, right = nums.length-1; // right也可能取nums.length,看查找结果的范围
while (left < right) { // 注意,不是 <=
int mid = left + (right - left) / 2;
if ( mid 不满足区间条件 ) {
// 将左区间完全排除
left = mid + 1
} else {
// mid满足区间,所以包含mid
right = mid
}
}
}
// 排除右区间
int binarySearchFor(int[] nums, int target) {
int left = 0, right = nums.length-1; // right也可能取nums.length,看查找结果的范围
while (left < right) { // 注意,不是 <=
int mid = left + (right - left + 1) / 2;
if ( mid 不满足所在区间 ) {
// 将右区间完全排除
right = mid - 1
} else {
// mid满足区间,所以包含mid
left = mid
}
}
}
四、一些LeetCode典型题目
1. 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
LeetCode地址
1 | class Solution { |
2. x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。
题目地址
1 | class Solution { |
3. 爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。
示例 1:
输入: piles = [3,6,7,11], H = 8
输出: 4
示例 2:
输入: piles = [30,11,23,4,20], H = 5
输出: 30
示例 3:
输入: piles = [30,11,23,4,20], H = 6
输出: 23
题目地址
1 | class Solution { |
4. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
题目地址
1 | class Solution { |
5. 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
题目地址
1 | class Solution { |
6. 搜索旋转排序数组 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
题目地址
1 | class Solution { |
7.寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
题目地址
1 | class Solution { |
8. 最长上升子序列
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:
可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
题目地址
1 | class Solution { |
9.寻找重复数
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明:
不能更改原数组(假设数组是只读的)。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字,但它可能不止重复出现一次。
题目地址
1 | class Solution { |
10.猜数字大小
猜数字游戏的规则如下:
每轮游戏,系统都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了,系统会告诉你这个数字比系统选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0):
-1 : 系统选出的数字比你猜测的数字小
1 : 系统选出的数字比你猜测的数字大
0 : 恭喜!你猜对了!
示例 :
输入: n = 10, pick = 6
输出: 6
题目地址
1 | /** |
11.寻找两个正序数组的中位数
给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。
请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
题目地址
1 | class Solution { |
12. 第一个错误的版本
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。
题目地址
1 | /* The isBadVersion API is defined in the parent class VersionControl. |
13. 找到 K 个最接近的元素
给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较小的那个数。
示例 1:
输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]
示例 2:
输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]
题目地址
1 | class Solution { |