好的，今天来到了我们0基础学算法的第三期，今天我们为大家讲解一下二分查找的相关知识。

查找也是有特殊情况的，比如数列本身是有序的。这个有序数列是怎么产生的呢？有时它可能本身就是有序的，也有可能是我们通过之前所学的排序算法得到的。不管怎么说，我们现在已经得到了有序数列了并需要查找。这时二分查找该出场了。

概述

二分查找又称折半查找、二分搜索、折半搜索等，是在分治算法基础上设计出来的查找算法，对应的时间复杂度为O(logn)。

到这里是不是感觉很熟悉，我们前两期的算法知识，也是基于分治的方法去进行学习的，如果有这方面还不了解的朋友，你可以到我的https://developer.aliyun.com/article/1003294?spm=a2c6h.26396819.creator-center.18.47163e18uolOT9

里面去查看一下。

二分查找理解

二分查找就是使用二分查找算法搜索目标元素的核心思想是：不断地缩小搜索区域，降低查找目标元素的难度。

我们现在在网络上去寻找二分查找的知识时，有很多教程在讲解二分查找的实现时，向我们讲解的是，在一个升序的列表中；也就是都会提到一个顺序的列表的前提条件。确实顺序列表可以使用二分查找，但是这也会给我们造成一个误解，只有顺序列表才能使用二分查找，其实并不是这样的，在这里我强调一下：

有顺序或者是有单调性一定可以二分查找；但是，可以二分查找并不一定有单调性。

所以对于二分查找我们这样理解即可：也就是给定我们一个区间，有一个条件，它可以将我们这个区间去分成左右两个部分（这两个部分可以不相邻）；这时我们就可以去使用二分查找的方法了。

看完上面的知识，我们就可以了解到，什么时候可以使用二分查找，这个知识很重要，因为我们在学习算法时，会接触到很多很多知识，你学完所有的知识，也都熟悉掌握了，但是你不知道什么时候用什么知识，这样会大大降低你写题的效率，所有学会什么时候使用知识，这也是我们学习的重点之一。

二分查找实现

下面，我们就开始正式的讲解二分查找了，我们将二分查找分成两个部分：整数二分、实数二分。其中整数二分是最麻烦的，因为如果我们处理不好边界问题，会很容易的造成死循环，实数二分就很简单，如果我们可以正确的理解掌握整数二分，那么实数二分就是不在话下的。

举例说明

在这里我们给出一串数字，想要查找3数字对应的下标范围。

这时我们就要使用二分查找了，我们通过观察图片可以看出数字3的范围是 [3,4] 。

第一步我们先找中点，即中点是2 。

这时我们判断2是小于三的，所以我们左半边的部分可以一并砍掉，留下右半边。(判断条件 Mid >= x ;可以暂时不考虑，先学习大致方法)

这时我们再次找中点，即：4 。

这时我们判断3>=3, 满足条件，所以更新右半边。

这时我们继续进行判断，Mid：3 ；满足条件，所以更新区间，这一次更新区间后下标就只有3了，这时我们也成功的把左半下标成功找到。

然后我们判断一下是否有解，也就是最后更新的区间最边界值是否等于我们想要求的值，如果相等那么就是存在，如果不相等，就是不存在。

之后我们如法炮制的去进行求右半边点，这时求右半边的点要求就变成了判断 Mid <= x ；

这时我们进行计算Mid跟左半边不太一样，这里到下面讲解时会讲些。

由于3<=3 满足条件，所以将左半边删去，因为这时就算有右半边范围也只可能时Mid点，也不可能在Mid点前面。

这时我们继续计算Mid点，即：4 .

这时继续判断，发现3<=3 ;所以砍掉左边部分 ；

这时我们继续计算中点，发现Mid：5 ；此时4>3 ;所以不满足。

这时山区左半边就剩下一个元素，其对应的下标也就是我们的右半边了。

程序结束。

完整流程以及笔记如下：

整数二分

其实整数二分的本质也就是边界问题了。在这里，我们将会为大家提供两个模板，提前剧透一下这两个模板的根本区别就在于"+1"。

所以这两个模板也就是求两个边界点的模板，就是图中红色斑块模板和蓝的板块的模板。

模板讲解

我们将整数二分成了两个板块，那么我们下面就来分析一下这两个板块了。

红色区间：

1.取Mid点为中间点。

2.判断mid点。（后面详细讲解）

3.判断是否满足：（l、r初始为左右端点）

       满足：更新区间, l=mid ;

       不满足：更新区间，r=mid-1；

蓝色区间：

1.取Mid点为中间点。

2.判断mid点。（后面详细讲解）

3.判断是否满足：（l、r初始为左右端点）

       满足：更新区间, r=mid ;

       不满足：更新区间，l=mid+1；

看了上面的部分，我们就对二分查找的整个流程就有了一个具体的认识，那么下面我们就要对二分查找的细节去进行一个详细的解释了。

二分查找细节

首先，我们要知道的是，题目中l,r在最初始时是数组的左右两端点，并且这里给出一个数组a来方便我们理解。

对于mid点

mid点也就是数组的中点下标，其结果是（l+r)/2,但是切记如果我们在使用红色区间的模板时，mid点需要设为：（l+r+1)/2;

其原因主要是因为在C++中除法是进行向下取整的，当 l = r-1 的时候，我们进行红色区域的操作时，（l+r）/2 = l ；这个时候如果我们正确的话，更新区间为l=mid，但mid=l；所以这时就进入到了一个死循环中，于是算法就不成立，这时我们+1后就可以完美解决这个问题了。

那么在使用的时候我们应该怎么样取规避掉这些错误呢？

在这里教给大家一个简单的方法，就是我们刚开始也不用管是否+1，先写，在判断条件的时候，如果成立情况下，是要 l=mid 这时就需要进行+1的操作了，否则的话，我们就不需要进行 +1 的操作。

如何判断变换左右点

平时在这方面一直会有朋友来问，我应该怎么样判断我需要取的点是 l=mid 还是 r=mid 以及还有怎么判断是该 l = mid+1, 为啥要 +1 而不是 -1 啊？

这里我们还是要从回归模板本质，我们设想一下，如果给出我们一个有序数组，让我们取找到其中一个数（num）的位置，那么当我们的 a[mid] >= num 的时候，此时，min下标后面的元素全都不可能成为数字num的范围，因为min下标后面的数都比mid大，所以我们的num位置一定在左半区，这样我们就只需要更新r点就可以了，同理我们判断更新l的时候也是这样的。

那我们又应该如何去判断+1 -1的问题呢？这里我们继续使用上面的例子，如果a[mid]>=num不成立，那么这个时候mid点以及mid点左半部分，就一定不会是num的范围，这时我们应该更新l，但l为什么是mid+1呢？一位我们前面判断的时候判断条件是 >= 也就是，不满足此条件的就不可能出现 = num 的情况，所以mid必不可能在num的范围内。

那为什么我们上面的判断不需要 +1 -1呢？因为上面我们使用的是大于等于，所以有一种 a[mid]=num的情况需要我们去考虑，那这个mid很有可能就是其边界点，这时我们就不可以去进行 +1 -1的操作。

模板实现

红色区域情况

bool check(int x) {/* ... */}   // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int red(int l, int r)
{
  while (l < r)
  {
    int mid = (l + r)/2 ;
    if (check(mid)) r = mid;    // check()判断mid是否满足性质
    else l = mid + 1;
  }
  return l;
}

蓝色区域情况：

bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bule(int l, int r)
{
  while (l < r)
  {
    int mid = (l + r + 1)/2;
    if (check(mid)) l = mid;
    else r = mid - 1;
  }
  return l;
}

注意注意：当true需要执行 l=mid时，计算mid的时候就需要 +1 。

实数二分

对于实数二分就是一种比较简单的二分方法了，就比如我们想要求一个数的三次方根就可以使用这种方法。

在这可能有朋友会产生两个问题；

第一，为什么求三次方根可以使用二分查找。我们思考一下我在讲二分查找的时候我说过的一句话，也就是给定我们一个区间，有一个条件，它可以将我们这个区间去分成左右两个部分（这两个部分可以不相邻）；这时我们就可以去使用二分查找的方法了。那咱们看一下这个情况，我们将这个数的三次方根放入一个顺序的范围内，然后我们不断判断 a[mid]的三次方与我们要计算的数相比，这样是不是可以将其划分为左右两个部分；这是我们就满足的它的条件，那么我们也就可以去使用二分查找了。

第二，为什么二分查找可以去求得三次方，这里我们其实最后算出来的是一个范围，但是这个范围是足够的小，以至于我们在输出前几位数字的时候它不会有差别，所以也就是变向的计算出了其三次方根了。

实数二分模板

实数二分的模板就不分两部分了，他只有一种。

1.取Mid点为中间点。

2.判断mid点。

3.判断是否满足：（l、r初始为左右端点）

       满足：更新区间, r=mid ;

       不满足：更新区间，l=mid；

这样一看是不是就发现实数二分要比我们的整数二分要简单很多了。

模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
                                //通常我们要保存精度大两位
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

习题讲解

题目一 数的范围

题目描述

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

如果数组中不存在该元素，则返回“-1 -1”。

输入格式

第一行包含整数n和q，表示数组长度和询问个数。

第二行包含n个整数（均在1~10000范围内），表示完整数组。

接下来q行，每行包含一个整数k，表示一个询问元素。

输出格式

共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回“-1 -1”。

数据范围

1≤n≤100000

1≤q≤10000

1≤k≤10000

样例

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

思路

本题是练习二分很好的一道题目，二分程序虽然简单，但是如果写之前不考虑好想要查找的是什么，十有八九会是死循环或者查找错误，就算侥幸写对了也只是运气好而已。用二分去查找元素要求数组的有序性或者拥有类似于有序的性质，对本题而言，一个包含重复元素的有序序列，要求输出某元素出现的起始位置和终止位置，翻译一下就是：在数组中查找某元素，找不到就输出-1，找到了就输出不小于该元素的最小位置和不大于该元素的最大位置。所以，需要写两个二分，一个需要找到>=x的第一个数，另一个需要找到<=x的最后一个数。查找不小于x的第一个位置，较为简单。

int l = 0, r = n - 1;
while (l < r) {
    int mid = (l + r )/2;
    if (a[mid] < x)  l = mid + 1;
    else    r = mid;
}

当a[mid]小于x时，令l = mid + 1，mid及其左边的位置被排除了，可能出现解的位置是mid + 1及其后面的位置；当a[mid] >= x时，说明mid及其左边可能含有值为x的元素；当查找结束时，l与r相遇，l所在元素若是x则一定是x出现最小位置，因为l左边的元素必然都小于x。查找不大于x的最后一个位置 同理而言，查找不大于x的最后一个位置，当a[mid] <= x时，待查找元素只可能在mid及其后面，所以l = mid；当a[mid] > x时，待查找元素只会在mid左边，令r = mid。

AC

#include <iostream>
using namespace std ;
const int N = 100010 ;
int a[N] ;
int main()
{
  int n , q ;
  cin >> n >> q;
  int num , mid , l, r ;
  for(int i=0; i<n; i++)
  {
    cin >> a[i] ;
  }
  while(q--)
  {
    cin >> num ;
    l = 0, r = n-1 ;
    while(l<r)  //判断，当l=r时停止
    {
      mid = (l+r)/2 ; //调用模板
      if(a[mid]>=num)
      {
        r = mid ;
      }
      else
      {
        l = mid+1 ;
      }
    }
    if(a[l] != num) cout <<"-1 -1" << endl ;  //如果不存在输出
    else{
      cout << l << " " ;  //输出左半边下标
      l = 0, r = n-1 ;
      while(l<r)
      {
        mid = (l+r+1)/2 ;
        if(a[mid]<=num)
        {
          l = mid ;
        }
        else{
          r = mid - 1 ;
        }
      }
      cout << l << endl ; //输出右半边下标
    }
  }
  return 0 ;
}

在这里需要提醒的是，题目中说不存在该元素，并不是我们的二分查找没有结果，这两个意思是不用的，我们的二分查找模板是一定会输出一个范围的，只是当数组中不存在该元素会输出的范围是特定的，所以通过我们判断这个范围去判断是否存在该元素，并不是我们的二分查找没有结果。

题目二 数的三次方根

给定一个浮点数 n，求它的三次方根。

输入格式

共一行，包含一个浮点数 n。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

数据范围

−10000≤n≤10000−10000≤n≤10000

输入样例：

1000.00

输出样例：

10.000000

思路：

对于这道题目实质上就是考察了我们二分的相关知识，也就是我们将这个三次方的数设定一根范围，在这个范围内去不断缩小这个数的大小范围，知道缩小到我们想要的结果为止。

具体流程如下：

在这里，结果是想要保留六为小数，所以我们将结果的范围控制在10^-8以内就可以了，这时不论我们输出 l 还是输出 r ，保留六位小数的结果都是相同的。

AC：

#include<iostream>
using namespace std ;
int main()
{
  double x ;
  cin >> x ;
  double l = -10000, r = 10000 ;    //范围
  double num = 1e-8 ;    //设置精度
  while(r-l >= num)        //调用模板
  {
    double mid = (l+r)/2 ;
    if(x >= mid*mid*mid)
    {
      l = mid ;
    }
    else{
      r = mid ;
    }
  }
  printf("%.6lf", l) ;        //保留小数
  return 0 ;
}

到这里我们的二分查找也就讲解结束了，希望大家都可以听懂，如果还有什么不会的可以在评论下面提出，我看到后就会立即回复的。也希望大家可以多多支持，加油！一起进步。

当然在最后也向大家推荐一个刷题的网站：