theme: v-green
大家好,我是饼干酱,在力扣刷过700+题,虽然是个小前端,但是对算法一直很热爱。
总是看到有人说不会二分,也看到过各种总结的文章,写得极其复杂,旧人懵逼,新人落泪。
但是就我 700+ 题的经验来说,二分真的很简单,从来不需要考虑那么多情况,所以决定写篇文简单讲述一下。
走过路过发现 bug 请指出,拯救一个辣鸡(但很帅)的少年就靠您啦!!!
什么是二分
解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性,则满足使用二分法的条件。把这里的枚举换成二分,就变成了“二分答案”。二分答案的时间复杂度是O(logN * (单次验证当前值是否满足条件的复杂度))
。
最简单的例子,猜 0-100
间的一个数字,每次告诉你大了还是小了,最小次数猜出。最优解就是每次取中间值,然后根据反馈去缩小范围。
画个图来理解,每次判断中间值是否合法之后,都可以把答案范围缩小一半。
简单来说,要进行二分法,需要两个条件
- 边界,我们必须要知道答案范围,有一个最小值和一个最大值,这个有时候题目没有直接给出但是可以自己推断出。
- 任意枚举一个值,可以根据这个值算出的结果来缩小答案范围
例1:二分查找
给定一个有序数组和一个数字 x
,快速查找数组中 x
的下标,不存在则返回 -1
。
题目中最重要的就是有序,既然有序,每次我们判断某个数字后,都可以把范围缩小一半。
/**
* 在有序数组 arr 中查找 x 的下标 不存在返回-1
* @param {number[]} arr
* @param {number} x
*/
function biSearch(arr, x) {
// 返回的结果是下标 则范围在 0 ~ arr.length-1
let l = 0,
r = arr.length - 1;
while (l <= r) {
let mid = Math.floor((l + r) / 2);
if (arr[mid] === x) {
// 找到答案直接返回
return mid;
}
if (arr[mid] > x) {
// mid>x 证明 [mid,r] 都大于 x 所以要在小于 mid 的部分查找答案
// 把 r 设置为 mid-1,则查找范围缩小至 [l,mid-1]
r = mid - 1;
} else {
// 同理,mid<x 也要缩小范围
l = mid + 1;
}
}
return -1;
}
console.log(biSearch([1, 2, 3, 5, 8, 13, 21], 3)); // 2
console.log(biSearch([1, 2, 3, 5, 8, 13, 21], 7)); // -1
例2:[Easy] LeetCode 69. x 的平方根
给你一个非负整数
x
,计算并返回x
的 算术平方根 。由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意: 不允许使用任何内置指数函数和算符,例如
pow(x, 0.5)
或者x ** 0.5
。
这是一个典型的二分题目,朴素的思路,我们需要做的就是枚举答案,从 1~x
去计算,直到碰到某个数字的平方大于 x
,则停止枚举,但这样的复杂度是 O(N)。
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
let i
for (i = 1; i <= x; i++) {
if (i * i > x) break
}
return i - 1
};
其实并不需要枚举每个数字,我们知道 f(x)=x^2
是一个单调递增函数,所以如果对于任何一个数字 i
,如果 i^2 < x
我们就知道任何小于 i
的数字,它的平方都小于 x
,反之亦然。
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
let l = 0, r = x; // 根据题目要求 答案可能的值最小为0 最大为x
let ans = 0; // 记录最终答案
while (l <= r) {
let mid = Math.floor((l + r) / 2); // 取中间值
if (mid * mid <= x) { // 判断中间值是否合法
// 合法的值,更新答案并缩小范围
ans = mid;
l = mid + 1;
} else {
// 不合法的值,只缩小范围
r = mid - 1;
}
}
return ans;
};
例3:[Middle] LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组
nums
,和一个目标值target
。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target
,返回[-1, -1]
。你必须设计并实现时间复杂度为
O(log n)
的算法解决此问题。
这里求两个值,要写两个二分查找的函数。二分查找的代码其实都很像,无非是一个左边界一个右边界,然后循环中计算中间值,然后和目标进行比较,我们需要判断的就是中间值和目标值比较时,在大于等于小于三种情况时,分别要做什么。对于此题来说,重点在于等于时要如何操作,详情看下面代码注释。
// 二分查找等于target的最小下标
function biSearchStart(nums, target) {
let l = 0, r = nums.length - 1;
let ans = -1;
while (l <= r) {
let mid = Math.floor((l + r) / 2);
const val = nums[mid]
if (val < target) {
// 小于target需要保留右侧值
l = mid + 1
} else if (val === target) {
// 等于也不能返回,因为有多个值等于target
// 但是我们求的是最左侧的那个,所以记录答案,同时把范围向左缩小 继续计算
ans = mid
r = mid - 1
} else {
// 大于target需要保留左侧值
r = mid - 1
}
}
return ans
}
// 二分查找等于target的最大下标
function biSearchEnd(nums, target) {
let l = 0, r = nums.length - 1;
let ans = -1;
while (l <= r) {
let mid = Math.floor((l + r) / 2);
const val = nums[mid]
if (val < target) {
// 小于target需要保留右侧值
l = mid + 1
} else if (val === target) {
// 等于也不能返回,因为有多个值等于target
// 对比 biSearchStart 只需要调整这里的逻辑即可
// 因为这里求的是最大下标,所以保留右侧的范围
ans = mid
l = mid + 1
} else {
// 大于target需要保留左侧值
r = mid - 1
}
}
return ans
}
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
return [biSearchStart(nums, target), biSearchEnd(nums, target)]
};
例4:[Middle] 2064. 分配给商店的最多商品的最小值
给你一个整数
n
,表示有n
间零售商店。总共有m
种产品,每种产品的数目用一个下标从 0 开始的整数数组quantities
表示,其中quantities[i]
表示第i
种商品的数目。你需要将 所有商品 分配到零售商店,并遵守这些规则:
- 一间商店 至多 只能有 一种商品 ,但一间商店拥有的商品数目可以为 任意 件。
- 分配后,每间商店都会被分配一定数目的商品(可能为
0
件)。用x
表示所有商店中分配商品数目的最大值,你希望x
越小越好。也就是说,你想 最小化 分配给任意商店商品数目的 最大值 。请你返回最小的可能的
x
。示例:
输入: n = 6, quantities = [11,6] 输出: 3 解释: 一种最优方案为: - 11 件种类为 0 的商品被分配到前 4 间商店,分配数目分别为:2,3,3,3 。 - 6 件种类为 1 的商品被分配到另外 2 间商店,分配数目分别为:3,3 。 分配给所有商店的最大商品数目为 max(2, 3, 3, 3, 3, 3) = 3 。
我们需要把商品分给商店,第 i
种商品有 quantities[i]
个,如果每家最多分 x
个,那么最小需要 ceil(quantities[i]/x)
个商店才能分配完,所以所有的商品需要∑(ceil(quantities[i]/x)),(0<=i<n)
个商店才能分配完。
总而言之, x
越小,需要的商店越多,我们枚举 x
来判断商店是否足够,并根据结果去缩小 x
的范围。
function isValid(n, quantities, x) {
let count = 0
for (let i = 0; i < quantities.length; i++) {
count += Math.ceil(quantities[i] / x)
}
return count <= n
}
/**
* @param {number} n
* @param {number[]} quantities
* @return {number}
*/
var minimizedMaximum = function(n, quantities) {
let l = 1, r = 100000
let ans = l
while (l <= r) {
let mid = Math.floor((l + r) / 2)
if (isValid(n, quantities, mid)) {
// 如果当前mid合法 我们就记录答案 然后再尝试小于mid的值中是否有合法值
ans = mid
r = mid - 1
} else {
// 如果不合法就缩小范围,去大于mid的值只查找
l = mid + 1
}
}
return ans
};
代码模板
经过上面的几个例子,你会发现,我们完全不需要考虑 while
循环的条件,直接写成 l<=r
即可,不过需要注意的是,我们需要额外维护一个 ans
来记录答案,当我们需要满足答案的值就更新 ans
。
其次,模板中的最重要的就是 isValid
函数,我们需要根据题意去实现这个函数,并更新 l
和 r
以及 ans
的值。
// isValid 判断某个值是否合法 根据题目要求实现
// 假设 如果x合法则大于x一定合法 如果x不合法则小于x一定不合法
// 求最小合法值
function binaryCalc() {
let l = 0, r = 10000; // 答案可能出现的最小值l和最大值r 根据题目设置具体值
let ans; // 最终答案
while (l <= r) {
let mid = Math.floor((l + r) / 2); // 取中间值,记得要加floor 不然算出来的是小数
if (isValid(mid)) {
// 如果 mid 合法 则 [mid, r] 都是合法的
// 我们先把ans设置为当前获取的合法值的最小值 mid
ans = mid;
// 然后再去继续去求[l,mid-1]里面是否有合法值
r = mid - 1;
} else {
// 如果mid不合法 则[l,mid]都是不合法的
// 我们去[mid+1,r]中找答案
l = mid + 1;
}
}
return ans;
}
本文正在参加「金石计划 . 瓜分6万现金大奖」
暂无评论内容