Java教程
初始简单算法
前言
二分查找，又叫二分枚举是在一个单调有序的数组中查找某个元素的搜索算法。原理比较简单，基本说一遍就知道是怎么一回事。然而，实际过程中，很容易写错，比如：
1）左区间是加一还是不加？
2）右区间是减一还是不减？
3）迭代的终止条件怎么写？
4）为什么有时候会死循环？
带着以上几个疑问，这篇文章将对二分查找的所有写法进行一个归纳总结。
点我 获取 粉丝专属 《算法和数据结构》源码，以及获取博主的联系方式。
文章目录
- 前言
- 一、线性枚举
- 1、线性枚举定义
- 2、举例说明
- 3、算法分析
- 1）前提
- 2）条件
- 3）返回结果
- 4、画解枚举
- 1）划分
- 2）游标
- 3）遍历
- 4）详解
- 5、举一反三
- 1）大于 x x x 的最小数的下标
- 2）大于等于 x x x 的最小数的下标
- 3）小于 x x x 的最大数的下标
- 4）小于等于 x x x 的最大数的下标
- 6、时间复杂度
- 二、二分枚举
- 1、二分枚举定义
- 2、举例说明
- 3、算法分析
- 1）目标
- 2）游标
- 3）二分
- 4）时间复杂度
- 4、源码详解
- 1）条件判定
- 2）二分枚举模板
- 5、细节解析
- 1）迭代的过程
- 2）结束条件
- 3）游标初始值
- 4）中点位置
- 5）死循环
- 三、二分枚举的应用
- 1、数组精确查找
- 1）题目描述
- 2）算法分析
- 3）源码示例
- 2、线性枚举 + 数组精确查找
- 1）题目描述
- 2）算法分析
- 3）源码示例
- 3、数组的模糊查找
- 1）大于等于 x x x 的最小值
- 2）大于 x x x 的最小值
- 3）小于等于 x x x 的最大值
- 4）小于 x x x 的最大值
- 4、单调函数的查找
- 1）题目描述
- 2）算法分析
- 3）源码示例
- 四、二分枚举的通解
- 粉丝专属福利
一、线性枚举
1、线性枚举定义
线性枚举指的就是遍历某个一维数组（顺序表）的所有元素，找到满足条件的那个元素并且返回，返回值可以是下标，也可以是元素本身。
由于是遍历的，穷举了所有情况，所以一定是可以找到解的，一些资料上也称之为 暴力算法 （Brute Force）。接下来，我们通过一个例子来理解 线性枚举。
2、举例说明
【例题1】给定一个单调不降的有序数组 a r r arr arr 和 一个值 x x x，要求找到大于 x x x 的最小数的下标。
3、算法分析
我们从这个问题中提取几个关键字并分类如下：
1）前提：单调不降、有序；
2）条件：大于
x
x
x、最小数；
3）返回结果：下标；
1）前提
前提就是问题给定时的初始数组需要满足的先天性条件，保证数据是能够符合这个前提的。这里的前提是 数组一定是有序的，且是单调不降的，即 数组下标大的数 不会比 数组下标小的数 更小。
2）条件
这个问题中的条件有两个：
1）大于
x
x
x ；
2）值最小；
我们如果仔细分析一下这个问题，就可以发现，正因为这里的数组是单调不降的，所以，一旦满足 某个数大于
x
x
x，之后的所有数必然都满足 大于
x
x
x 这个条件。所以我们必然可以把数组分成两部分，一部分是 大于
x
x
x 的，另一部分是 不大于
x
x
x 的。
3）返回结果
这里的返回结果要求是下标，而我们遍历操作也是通过遍历数组的下标进行的，所以找到满足条件的，返回下标即可。
4、画解枚举
接下来，我们通过一组实际的数据来解释这个问题。
a
r
r
=
[
1
,
3
,
4
,
6
,
6
,
6
,
7
,
8
,
9
]
arr = [1, 3, 4, 6, 6, 6, 7, 8, 9]
arr=[1,3,4,6,6,6,7,8,9]
1）划分
对于这个数组，当
x
=
6
x = 6
x=6 时，我们将数组分成两部分，大于 6 的部分用 绿色表示，不大于 6 的部分用红色表示。
这么表示的目的，主要是为了方便记忆，联想一下 红绿灯，绿色代表可以通行，即 “大于6” 这个条件满足；红色代表禁止通行，即条件不满足。
2）游标
设定一个游标，初始时指向数组的第 0 个元素（C语言中数组下标从 0 开始计数）。
游标，顾名思义，就是游动的下标。你也可以叫指针，我之所以没有称之为指针，是不想它和C语言中的指针概念混淆。
3）遍历
遍历就是判断当前游标指向的元素是否是绿色的，如果是绿色的直接返回，因为它一定是大于 x x x 且值最小的；如果不是，则增加游标的值，继续下一次判断，直到数组遍历完毕。如下图所示：
数字 7 就是我们要找到 大于 6 的最小数，它的下标为 6。
4）详解
int isGreen(int val, int x) { // (1)
return val > x;
}
int findFirstBiggerThan(int *arr, int arrSize, int x) {
int i;
for(i = 0; i < arrSize; ++i) { // (2)
if( isGreen(arr[i], x) ) { // (3)
return i;
}
}
return arrSize; // (4)
}
-
(
1
)
(1)
(1)
int isGreen(int val, int x)这个函数代表条件是否满足，满足返回 1，否则返回 0；这里的条件便是 v a l > x val > x val>x。 - ( 2 ) (2) (2) 下标从小到大，从 0 开始遍历数组 a r r arr arr；
- ( 3 ) (3) (3) 一旦遇到大于 x x x 的数，则返回它的下标，因为是下标从小往大遍历的，所以第一个找到满足条件的数一定是值最小的；
- ( 4 ) (4) (4) 如果找不到，说明所有的数都是小于等于 x x x 的，直接返回数组长度；
5、举一反三
接下来，我们来看看线性枚举的其它几种问法。
【例题2】给定一个单调不降的有序数组如下： [ 1 , 3 , 4 , 6 , 6 , 6 , 7 , 8 , 9 ] [1, 3, 4, 6, 6, 6, 7, 8, 9] [1,3,4,6,6,6,7,8,9]。要求找到以下元素：
( 1 ) (1) (1) > 6 \gt 6 >6 的 最小数 的下标位置；
( 2 ) (2) (2) ≥ 6 \ge 6 ≥6 的 最小数 的下标位置；
( 3 ) (3) (3) < 6 \lt 6 <6 的 最大数 的下标位置；
( 4 ) (4) (4) ≤ 6 \le 6 ≤6 的 最大数 的下标位置；
对于这四个问题，我们可以发现它们的答案如下所示：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 3 | 4 | 6 | 6 | 6 | 7 | 8 | 9 |
| ( 3 ) (3) (3) | ( 2 ) (2) (2) | ( 4 ) (4) (4) | ( 1 ) (1) (1) |
1）大于 x x x 的最小数的下标
将数组按照条件进行划分，然后利用上文提到的findFirstBiggerThan函数求解即可。
2）大于等于 x x x 的最小数的下标
我们把问题做个变形，将问题变成找 大于等于 x x x 的最小数的下标（比之前的问题多了一个等于）。按照条件划分的结果应该是包含 6 本身的，所以如下图所示：
遍历数组的部分不变，只不过条件变成了 大于等于。C语言实现如下：
int isGreen(int val, int x) {
return val >= x; // (1)
}
int findFirstBiggerEqualThan(int *arr, int arrSize, int x) {
int i;
for(i = 0; i < arrSize; ++i) {
if( isGreen(arr[i], x) ) {
return i;
}
}
return arrSize;
}
-
(
1
)
(1)
(1) 将原先的
>号改成>=即可；
3）小于 x x x 的最大数的下标
上面两个问题能理解的话，我们再来看一个问题，如何找到 小于 x x x 的最大数的下标 ，要求下标最大，那么我们在枚举的过程中，如果发现一个大于等于 x x x 的数，那么后续都不用枚举了，并且需要返回这个数的前一个位置。条件划分如下图所示：
我们要做的是返回红色中的最大下标，C语言实现如下：
int isGreen(int val, int x) {
return val >= x; // (1)
}
int findLastSmallThan(int *arr, int arrSize, int x) {
int i;
for(i = 0; i < arrSize; ++i) {
if( isGreen(arr[i], x) ) {
return i - 1;
}
}
return arrSize - 1;
}
-
(
1
)
(1)
(1) 大于等于
x
x
x 时，
isGreen成立； - ( 2 ) (2) (2) 由于我们要做的是返回红色中的最大下标，所以一旦遇到大于等于 x x x 的数（即绿色的情况），则返回它的前一个下标；
-
(
3
)
(3)
(3) 如果找不到，则返回
arrSize - 1，即所有数都是红色的，则最大下标就是数组的最后一个元素的下标；
4）小于等于 x x x 的最大数的下标
我们把问题继续做变形，将问题变成找 小于等于 x x x 的最大数的下标（比之前的问题多了一个等于）。划分如下图所示：
遍历数组的部分不变，只不过条件变成了 大于，我们要做的是返回红色中的最大下标，C语言实现如下：
int isGreen(int val, int x) {
return val > x; // (1)
}
int findLastSmallEqualThan(int *arr, int arrSize, int x) {
int i;
for(i = 0; i < arrSize; ++i) {
if( isGreen(arr[i], x) ) {
return i - 1;
}
}
return arrSize - 1;
}
-
(
1
)
(1)
(1) 将原先的
>=号改成>即可；
6、时间复杂度
以上的内容就是线性枚举的几种常见情况，也就是无脑遍历所有情况，并且在满足条件的第一时间退出循环，当数组长度为
n
n
n 时，算法的时间复杂度为
O
(
n
)
O(n)
O(n)，比较低效，有没有更加高效的算法呢？
接下来出场的，就是本文的主角 —— 二分枚举。
二、二分枚举
1、二分枚举定义
二分枚举，也叫二分查找，指的就是给定一个区间，每次选择区间的中点，并且判断区间中点是否满足某个条件，从而选择左区间继续求解还是右区间继续求解，直到区间长度不能再切分为止。
由于每次都是把区间折半，又叫折半查找，时间复杂度为
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)，和线性枚举的求解结果一直，但是高效许多，返回值可以是下标，也可以是元素本身。
2、举例说明
【例题3】只有两种颜色的数组 a r r arr arr ，左边部分为红色用 0 表示，右边部分为绿色用 1 表示，要求找到下标最小的绿色元素的下标。
如图所示，下标最小的绿色元素的下标为 3，所以应该返回 3。
3、算法分析
1）目标
对于这个问题，当我们拿到这个数组的时候，第一个绿色位置在哪里，我们是不知道的，所以，现在的目标就是要通过二分枚举找到红色区域和绿色区域的边界。
2）游标
利用线性枚举的思路，我们引入游标的概念，只不过需要两个游标，左边一个红色游标，右边一个绿色游标。并且游标初始位置都在数组以外，对于一个 n n n 个元素的数组，红色游标初始位置在 − 1 -1 −1，绿色游标初始位置在 n n n。
3）二分
我们将两个游标相加，并且除 2，从而得到游标的中点，并且判断中点所在位置的颜色，发现是绿色的，这说明从 中点游标 到 绿色游标 的元素都是绿色的。如下图所示：
于是，我们可以把 绿色游标 替换成 中点游标，如下图所示：
这样就完成了一次二分，区间相比之前，缩小了一半。注意，我们要求的解，一定永远在 红色游标 和 绿色游标 之间。
然后，我们继续将两个游标相加，并且除 2，从而得到游标的中点，并且判断中点所在位置的颜色，发现是红色的，这说明从 红色游标 到 中点游标 的元素都是红色的。如下图所示：
于是，我们可以把 红色游标 替换成 中点游标，如下图所示：
同样上述算法，再经过两次二分以后，我们得到了如下结果：
这个时候，这个时候 红色游标 和 绿色游标 的位置一定相差 1，并且 绿色游标 的位置就是我们这个问题要求的解。
4）时间复杂度
由于每次操作都是将区间减小一半，所以时间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2n)。
4、源码详解
那么接下来，我们来看下，如何用 C语言来 实现这个问题。
1）条件判定
判断一个元素是绿色还是红色，我们可以单独用一个函数来实现，根据题意，当值为 1 时代表绿色，值为 0 时代表红色，C语言实现如下：
int isGreen(int val) {
return val == 1;
}
2）二分枚举模板
接下来的二分枚举模板可以解决大部分二分枚举的问题，请妥善保管。
int binarySearch(int *arr, int arrSize, int x) {
int l = -1, r = arrSize; // (1)
int mid;
while(r - l > 1) { // (2)
mid = l + (r - l) / 2; // (3)
if( isGreen(arr[mid], x) ) // (4)
r = mid; // (5)
else
l = mid; // (6)
}
return r; // (7)
}
- ( 1 ) (1) (1) l l l 代表 红色游标， r r r 代表 绿色游标；
- ( 2 ) (2) (2) 当区间长度大于 2 的时候，二分缩小区间，这一步被称为 区间收敛；
- ( 3 ) (3) (3) m i d mid mid 为计算出来的区间 [ l , r ] [l, r] [l,r] 的中点；
- ( 4 ) (4) (4) 判断区间中点对应的元素是 绿色 还是 红色；
- ( 5 ) (5) (5) 如果 中点元素 是 绿色，则从 中点 到 r r r 的值都为 绿色，用 中点 替换 绿色游标；
- ( 6 ) (6) (6) 如果 中点元素 是 红色，则从 l l l 到 中点 的值都为 红色，用 中点 替换 红色游标；
- ( 7 ) (7) (7) 这个地方是模板需要变通的地方，如果需要返回红色边界，那么应该返回 l l l；反之，如果需要返回绿色边界，则应该返回 r r r。这个问题中，是后者。
5、细节解析
1）迭代的过程
整个二分的过程是一个不断迭代区间的过程，并且 红色游标 指向的元素始终是 红色 的；绿色游标 指向的元素始终是 绿色 的。迭代的过程就是不断向 红绿边界 逼近的过程。
2）结束条件
迭代结束时，红色游标 和 绿色游标 刚好指向 红绿边界，且区间长度为 2。
3）游标初始值
为什么 红色游标 初始值为
−
1
-1
−1，绿色游标 初始值为
n
n
n ?
能否将 红色游标 初始化为
0
0
0，绿色游标 初始化为
n
−
1
n-1
n−1 ? 答案是否定的，试想一下，如果数据元素都是绿色，红色游标 初始化为 0 就违背了 " 红色游标 指向的元素始终是 红色 的 " 这个条件；反之，如果元素都是红色的，也有类似问题。
4）中点位置
由于中点的位置是需要去访问数组来获取值的，所以必须满足始终在
[
0
,
n
)
[0, n)
[0,n) 区间范围内。
中点位置计算公式为：
m
i
d
=
⌊
l
+
r
2
⌋
mid = \lfloor \frac {l +r} 2 \rfloor
mid=⌊2l+r⌋。
l
l
l 的最小值为
−
1
-1
−1，
r
r
r 的最小值为
l
+
2
l+2
l+2，所以
m
i
d
mid
mid 的最小值就是
⌊
l
+
r
2
⌋
=
⌊
−
1
+
(
−
1
+
2
)
2
⌋
=
0
\lfloor \frac {l +r} 2 \rfloor = \lfloor \frac {-1 + (-1 + 2)} 2 \rfloor = 0
⌊2l+r⌋=⌊2−1+(−1+2)⌋=0；
r
r
r 的最大值为
n
n
n，
l
l
l 的最大值为
r
−
2
r-2
r−2，所以
m
i
d
mid
mid 的最大值就是
⌊
l
+
r
2
⌋
=
⌊
n
+
(
n
−
2
)
2
⌋
=
n
−
1
\lfloor \frac {l + r} 2 \rfloor = \lfloor \frac {n + (n - 2)} 2 \rfloor = n-1
⌊2l+r⌋=⌊2n+(n−2)⌋=n−1；
综上所述，中点的下标位置始终在
[
0
,
n
)
[0, n)
[0,n) 区间范围内。
5）死循环
上面的程序模板是否会进入死循环？
我们可以这么来看，当区间为 2 时，循环结束。当区间为 3 时，它一定可以变成区间为 2 的情况，当区间为4时，一定可以变成区间为 2 或者 3 的情况，也就是任何一种情况下，区间一定会减小，并且当等于 2 时，循环结束。所以不会造成死循环。
三、二分枚举的应用
接下来，提供一个通用模板，利用这个模板，只需要修改isGreen函数，就能实现绝大部分的二分枚举问题。
/************** 二分查找 数组 模板 **************/
/*
1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；
2）返回值：绿色区段的左边界；
*/
int isGreen(int val, int x);
int binarySearch(int *arr, int arrSize, int x) {
int l = -1, r = arrSize;
int mid;
while(l + 1 < r) {
mid = l + (r - l) / 2;
if( isGreen(arr[mid], x) )
r = mid;
else
l = mid;
}
return r;
}
/************** 二分查找 数组 模板 **************/
其中，条件函数int isGreen(int val, int x)函数的实现需要根据具体问题具体分析。
1、数组精确查找
1）题目描述
【例题4】给定一个 n n n 个元素的升序整型数组 n u m s nums nums 和一个目标值 x x x，写一个函数
search搜索 n u m s nums nums 中的 t a r g e t target target，如果目标值存在返回下标，否则返回 − 1 -1 −1。
原题链接：WhereIsHeroFrom/118445716
2）算法分析
对于查找
t
a
r
g
e
t
target
target 是否存在，我们把数组中 "大于等于
t
a
r
g
e
t
target
target" 的划分为 绿色，其它为红色，利用模板得到返回值，返回值返回的是
r
r
r，也就是图中的绿色箭头指向位置。需要分三种情况讨论：
1）
r
=
n
r = n
r=n，所有数都小于
t
a
r
g
e
t
target
target，返回-1；
2）
n
u
m
s
[
r
]
≠
t
a
r
g
e
t
nums[r] \neq target
nums[r]=target，代表这个值不存在，返回-1；
3）
n
u
m
s
[
r
]
=
t
a
r
g
e
t
nums[r] = target
nums[r]=target，直接返回
r
r
r；
时间复杂度为
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)。
3）源码示例
int isGreen(int val, int x) {
return val >= x; // (1)
}
int search(int* nums, int n, int x){
int r = binarySearch(nums, n, x); // (2)
if(r == n || nums[r] != x) // (3)
return -1;
return r; // (4)
}
- ( 1 ) (1) (1) 划分绿色边界；
- ( 2 ) (2) (2) 调用模板，返回绿色边界；
- ( 3 ) (3) (3) 没有找到解情况；
- ( 4 ) (4) (4) 找到解的情况；
2、线性枚举 + 数组精确查找
1）题目描述
【例题5】输入一个递增排序的数组和一个数字 s s s，在数组中查找两个数，使得它们的和正好是 s s s。如果有多对数字的和等于s，则输出任意一对即可。
原题链接：WhereIsHeroFrom/118507985
2）算法分析
我们已经知道在一个数组中寻找一个数的算法，那么，我们只需要枚举一个确定的数
x
x
x，然后再在数组的剩余部分去查找
s
−
x
s-x
s−x 是否存在，就可以确定两个数的实际位置了，时间复杂度
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)。
即先做一次线性枚举，再做一次二分枚举。
3）源码示例
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int i, pos, base;
int *ret = (int *)malloc( sizeof(int) * 2 ); // (1)
*returnSize = 0; // (2)
for(i = 0; i < numsSize; ++i) {
base = i+1; // (3)
pos = search(nums+base , numsSize-base, target - nums[i]); // (4)
if(pos != -1) { // (5)
ret[0] = nums[i];
ret[1] = nums[pos+base];
*returnSize = 2;
return ret;
}
}
return ret;
}
-
(
1
)
(1)
(1) 利用
malloc申请一块内存空间，用于返回值； - ( 2 ) (2) (2) 将返回数据的长度设为 0，因为有可能无解；
-
(
3
)
(3)
(3) 升序数组中的两个数的和为
target，所以我们可以枚举nums[i]，并且在剩下的数组中枚举，剩下数组的偏移量为base = i + 1； - ( 4 ) (4) (4) 调用【例题4】中的精确查找，查找是否存在解；
-
(
5
)
(5)
(5) 返回值不等于
−
1
-1
−1 ，则代表
nums[i]和nums[pos+i+1]的和为target，返回这两个值组成的数组即可；
3、数组的模糊查找
1）大于等于 x x x 的最小值
【例题6】给定一个排序数组和一个目标值 t a r g e t target target，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
原题链接：WhereIsHeroFrom/118452682
首先，我们需要考虑一下，插入的这个位置，需要满足什么条件？
如果我们对数组进行划分，大于等于目标值的作为绿色元素，其余作为红色元素。如果有目标值，那么绿色元素的左边界就是我们要找的索引；如果没有目标值，那么红色的右边界一定比我们要插入的数小，绿色元素的左边界一定比我们要插入的元素大，所以绿色元素的左边界也是我们要找的索引。
综上所述，我们就是要找到绿色元素的左边界，直接套用上面的二分枚举的模板即可。其中isGreen函数实现如下：
int isGreen(int val, int x) {
return val >= x;
}
2）大于 x x x 的最小值
【例题7】给你一个排序后的字符列表
letters，列表中只包含小写英文字母。另给出一个目标字母target，请你寻找在这一有序列表里比目标字母大的最小字母。
原题链接：WhereIsHeroFrom/120754725
如果我们对数组进行划分，大于目标值的作为绿色元素，其余作为红色元素，那么显而易见，我们只要找到这个绿色元素的左边界，就找到了大于目标值的最小值。
综上所述，我们就是要找到绿色元素的左边界，直接套用上面的二分枚举的模板即可。其中isGreen函数实现如下：
int isGreen(int val, int x) {
return val > x;
}
3）小于等于 x x x 的最大值
【例题8】给你一个排序后的递增数组 和 一个目标值 t a r g e t target target，要求找到小于等于 t a r g e t target target 的最大值的下标。
如果我们对数组进行划分，大于目标值的作为绿色元素，其余作为红色元素，那么显而易见，我们只要找到这个红色元素的右边界，就找到了小于等于目标值的最大值。
综上所述，直接套用上面的二分枚举的模板，并且对返回值减一即可。其中isGreen函数实现如下：
int isGreen(int val, int x) {
return val > x;
}
4）小于 x x x 的最大值
【例题9】给你一个排序后的递增数组 和 一个目标值 t a r g e t target target，要求找到小于 t a r g e t target target 的最大值的下标。
如果我们对数组进行划分，大于等于目标值的作为绿色元素，其余作为红色元素，那么显而易见，我们只要找到这个红色元素的右边界，就找到了小于目标值的最大值。
综上所述，直接套用上面的二分枚举的模板，并且对返回值减一即可。其中isGreen函数实现如下：
int isGreen(int val, int x) {
return val >= x;
}
有关数组的模糊查找问题，列出表格如下：
| 模糊查找 | 绿色部分条件 | 返回值 |
|---|---|---|
| 大于等于 x x x 的最小值 | ≥ x \ge x ≥x | r r r |
| 大于 x x x 的最小值 | > x \gt x >x | r r r |
| 小于等于 x x x 的最大值 | > x \gt x >x | l l l |
| 小于 x x x 的最大值 | ≥ x \ge x ≥x | l l l |
4、单调函数的查找
二分查找除了能够在数组中找到可行解，也能够在单调函数中找到可行解，同样是将函数根据定义域划分成两部分，左边为红色，右边为绿色，然后找到边界红绿边界，根据实际情况选择红色边界或者绿色边界。
相应的，二分枚举的模板需要做适当的修改，传入的参数由原先的数组，变成了一个区间。C语言实现如下：
/**************二分查找模板 返回绿色边界**************/
int isGreen(int val, int x);
int binarySearch(int l, int r, int x) {
int mid;
while(l + 1 < r) {
mid = l + (r - l) / 2;
if( isGreen(mid, x) )
r = mid;
else
l = mid;
}
return r;
}
/**************二分查找模板 返回绿色边界**************/
1）题目描述
【例题10】给你一个非负整数 x x x ，计算并返回 x x x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分，小数部分将被舍去。
原题链接：WhereIsHeroFrom/119976200
2）算法分析
考虑
f
(
x
)
=
x
2
f(x) = x^2
f(x)=x2 这个函数，当
x
x
x 递增时，函数的值越来越大，是一个单调递增函数。我们现在要做的就是，找到
f
(
k
)
f(k)
f(k) 使得
f
(
k
)
f(k)
f(k) 小于等于
x
x
x，且尽量大，并且返回
k
k
k 的值。
当
x
=
0
x=0
x=0,
x
=
1
x=1
x=1 时，我们可以直接返回
x
x
x；当
x
>
1
x > 1
x>1时，我们构造红绿边界，所有
f
(
k
)
≤
x
f(k) \le x
f(k)≤x 的情况为红色，反之，
f
(
k
)
>
x
f(k) \gt x
f(k)>x 的情况为绿色，然后通过二分找到红色边界就是答案了。
3）源码示例
int isGreen(int val, int x) {
return (long long)val * val > x; // (1)
}
int mySqrt(int x){
int r;
if(x == 0 || x == 1) {
return x;
}
r = binarySearch(0, x, x); // (2)
return r - 1; // (3)
}
- ( 1 ) (1) (1) 构造绿色部分为 k 2 > x k^2 \gt x k2>x，那么红色部分就是 k 2 ≤ x k^2 \le x k2≤x；
- ( 2 ) (2) (2) 找到绿色边界；
- ( 3 ) (3) (3) 返回红色边界；
四、二分枚举的通解
任何可以用二分枚举来求解的问题，都可以抽象出一个单调函数，并且将单调函数划分成 红色 和 绿色 两部分，通过二分枚举求出 红绿边界，然后再根据条件来决定是返回 红色的右边界，还是绿色的左边界。简化为以下四步：
1）抽象出单调函数；
2）确定isGreen函数；
3）二分枚举求出红绿边界；
4）确定返回 红色边界 还是 绿色边界；
关于 「 二分查找 」 的内容到这里就结束了。
如果还有不懂的问题，可以通过 「 电脑版主页 」找到作者的「 联系方式 」 ，线上沟通交流。
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
-
Java项目开发入门：新手必读指南11-23
-
Java语音识别项目入门教程11-23
-
Java语音识别项目入门教程11-23
-
Java云原生入门11-23
-
Java云原生入门：从零开始构建云原生Java应用11-23
-
Java云原生入门：简单教程助你轻松上手11-23
