初始简单算法

本文主要是介绍初始简单算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言

二分查找，又叫二分枚举是在一个单调有序的数组中查找某个元素的搜索算法。原理比较简单，基本说一遍就知道是怎么一回事。然而，实际过程中，很容易写错，比如：
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）确定返回红色边界还是绿色边界；

关于 「二分查找」 的内容到这里就结束了。
如果还有不懂的问题，可以通过 「电脑版主页」找到作者的「联系方式」 ，线上沟通交流。

这篇关于初始简单算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

初始简单算法

前言

文章目录

一、线性枚举

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）源码示例

四、二分枚举的通解

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯