二分算法

First Post:

Last Update:

二分查找算法

知识点

  • 二分查找原理讲解
  • 在单调递增序列 a 中查找 x 或 x 的后继
  • 在单调递增序列 a 中查找 x 或 x 的前驱

二分查找算法讲解

枚举查找即顺序查找，实现原理是逐个比较数组 a[0:n-1] 中的元素，直到找到元素 x 或搜索整个数组后确定 x 不在其中。最坏情况下需要比较 N 次，时间复杂度是 O(n)，属于线性阶算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {  
    public int search(int[] nums, int target) {  
        int left = 0, right = nums.length;  
        while (left < right) {  
            int mid = left + ((right - left) >> 1); // 无符号右移等同于除以2取整  
            if (nums[mid] == target)  
                return mid;  
            else if (nums[mid] < target)  
                left = mid + 1;  
            else if (nums[mid] > target)  
                right = mid - 1; // 修改这里，应该是 mid - 1  
        }  
        return -1; // 如果循环结束还没有找到，说明目标值不存在于数组中  
    }  
}

折半查找的基本思想：

在有序表中（low, high, low<=high），取中间记录即 a[(high+low)/2] 作为比较对象。

  • 若给定值与中间记录的关键码相等，则查找成功。
  • 若给定值小于中间记录的关键码，则在中间记录的左半区继续查找。
  • 若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。

不断重复上述过程，直到查找成功或所查找的区域无记录，查找失败。

二分查找的特征：

  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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Step 1:

假设存在一个有序数组：
下标[ 0   1   2   3   4   5   6   7   8    9    10   11   12 ]
数据[ 7   14  18  21  23  29  31  35   38   42   46   49  52 ]
      ↑                                                   ↑
    low=0                                              high=12

                            mid=(low+high)/2
                            mid=(0+12)/2
                            mid=6
                            [mid]=31 > 14，所以选择左半部分

操作：
    此时令low不变，high=mid-1=5

Step 2:

下标[ 0   1   2   3   4   5   6   7   8    9    10   11   12 ]
数据[ 7   14  18  21  23  29  31  35   38   42   46   49  52 ]
      ↑                   ↑
   low=0                 high=5

            mid=(low+high)/2
            mid=(0+6)/2
            mid=3
            [mid]=21 > 14，所以选择左半部分

操作：
    此时令low不变，high=mid-1=2

Step 3:

下标[ 0   1   2   3   4   5   6   7   8    9    10   11   12 ]
数据[ 7   14  18  21  23  29  31  35   38   42   46   49  52 ]
      ↑       ↑
   low=0    high=2

            mid=(low+high)/2
            mid=(0+2)/2
            mid=1
            [mid]=14 = 14  找到答案

操作：
    返回下标

这个文本看起来更加清晰，修正了一些不规范的表达。

整数二分法常用算法模板

C++ 语言描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 在单调递增序列a中查找>=x的数中最小的一个（即x或x的后继）
while (low < high)
{
    int mid = (low + high) / 2;
    if (a[mid] >= x)
        high = mid;

    else
        low = mid + 1;
}

// 在单调递增序列a中查找<=x的数中最大的一个（即x或x的前驱）
while (low < high)
{
    int mid = (low + high + 1) / 2;

    if (a[mid] <= x)
        low = mid;

    else
        high = mid - 1;
}

Python 语言描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#在单调递增序列a中查找>=x的数中最小的一个（即x或x的后继）
while low<high:

  mid=(low+high)/2

  if(a[mid]>=x):
      high=mid

  else:
      low=mid+1

#在单调递增序列a中查找<=x的数中最大的一个（即x或x的前驱）
while low<high:

  mid=(low+high+1)/2

  if(a[mid]<=x):
      low=mid

  else:
      high = mid-1

Java 语言描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 在单调递增序列a中查找>=x的数中最小的一个（即x或x的后继）
while (low < high) {

    int mid = (low + high) / 2;

    if (a[mid] >= x)
      high= mid;

  else
      low = mid + 1;
}

// 在单调递增序列a中查找<=x的数中最大的一个（即x或x的前驱）
while (low < high) {

    int mid = (low + high + 1) / 2;

    if (a[mid] <= x)
      low = mid;

  else
      high = mid - 1;

}

此处我们先分整数的二分查找法的常用模版，关于实数的部分，我们后面再讲。

下面可能会有同学会疑问道：为什么采用这一套代码的而不是采用查找等于的 X？

是因为这样的适用范围更广，当有 X 时这套代码就返回 X 的位置。如果没有 X，就返回 <=x 的数中最大的一个或者 >=x 的数中最小的一个。

分巧克力

2017 年省赛真题链接。

题目描述: 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 $N$ 块巧克力，其中第 $i$ 块是 $H_i \times Wi$ 的方格组成的长方形。为了公平起见，

小明需要从这 $N$ 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

  1. 形状是正方形，边长是整数;
  2. 大小相同;

例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述:

第一行包含两个整数 $N,K$ ($1 \leq N, K \leq 10^5$)。

以下 N 行每行包含两个整数 $H_i,W_i$ ($1 \leq H_i, W_i \leq 10^5$)。

输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述:

输出切出的正方形巧克力最大可能的边长。

输入输出样例:

示例:

输入

1
2 10 6 5 5 6

输出

1
2

运行限制:

  • 最大运行时间：2s
  • 最大运行内存: 256M

注意：

  1. 请严格按要求输出，不要画蛇添足地打印类似：“请您输入…”的多余内容。
  2. 不要调用依赖于编译环境或操作系统的特殊函数。
  3. 所有依赖的函数必须明确地在源文件中
  4. 不能通过工程设置而省略常用头文件。

题目分析

简单思路，边长的最大规模为 $100000$；我们可以枚举出所有的情况。按从大到小的顺序进行切割，直到找到满足要求的巧克力边长。

在判断边长是否满足条件时：求一块长方形$（h * w）$最多被分成的正方形$（len * len）$巧克力个数为：

$cnt = (h / len) * (w / len)$

xxxxxxxxxx43 1import os2import sys3​4import heapq5​6a = []7b = []8​9n,k = map(int,input().split())10​11for _ in range(n):12  x,y = map(int,input().split())13  a.append(x)14  b.append(y)15​16​17q = []18​19for i in range(n-1):20  heapq.heappush(q,(a[i],i))21​22​23t = k24​25ans = 026​27while t > 0:28  w,i = heapq.heappop(q)29​30  heapq.heappush(q,(b[i],i))31  ans += w32  t -= 133​34​35ans2 = 036if k >= n:37  ans2 += sum(a) + (k-n) * min(b)38​39​40if k >= n:41  print(min(ans,ans2))42else:43  print(ans)python

即用在单调递增序列 $a$ 中查找 $<=x$ 的数中最大的一个（即 $x$ 或 $x$ 的前驱）即可，原本这里的条件是 $<=x$ ，我们将其换成验证即可。

代码解答

C++ 实现：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>

using namespace std;
const int MAXN=100010;
int n,k;
int h[MAXN],w[MAXN];

bool pd(int l)
{
    int sum=0;
    for(int i=0; i<n; i++)
    {
        sum+=(h[i]/l)*(w[i]/l);
        if(sum>=k)
        {
            return true;
        }
    }
    return false;
}

int main()
{
    cin>>n>>k;
    for(int i=0; i<n; i++)
        cin>>h[i]>>w[i];

    //找到二分查找的上界
    int high=0;

    for(int i=0; i<n; i++)
    {
        high=max(high,h[i]);
        high=max(high,w[i]);
    }
    // 二分下届由题意可得至少为1
    int low=1;

    // 由于本题目就是求符合要求的Mid 值所以要将mid定义在二分查找外边
    int mid=0;
    while(low<high)
    {

        mid = (low + high+1) / 2;
        if(pd(mid))
            low=mid;
        else
            high = mid - 1;

//        cout<<low<<" "<<high<<endl;
    }

    //因为low=high所以输出哪一个都一样
    cout<<low;
    return 0;
}

查找上界这里可以直接输入的时候查询，这道题实际上是可以少次操作的，代码如下。

Python 实现

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
N=K=0
h=[]
w=[]
def pd(l):

 sum1=0
 for i in range(N):

   sum1+= (h[i]//l)* (w[i]//l)
   # Java C++ 的除法都是自己取整，Python会换成小数，Python的取整除法是//

   if sum1>=K :
       return True

 return False

if __name__ == '__main__':

   inFor = input().split()

   N=int(inFor[0])
   K=int(inFor[1])

   #找到二分查找的上界
   high=0

   for _ in range(N):
       wi, hi = map(int, input().split())
       w.append(wi)
       h.append(hi)
       high=max(high,max((hi,wi)))

   # 二分下届由题意可得至少为1
   low=1
   #由于本题目就是求符合要求的Mid 值所以要将mid定义在二分查找外边
   mid=0

   while low<high :

       mid= int ( (low+high+1)//2)
       if pd(mid):
           low=mid
       else:
           high=mid-1

   #因为low=high所以输出哪一个都一样
   print(low)

Java 实现

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.Scanner;
import static java.lang.Integer.max;

public class Main {

  static int n, k;
  static int h[] = new int[100005];
  static int w[] = new int[100005];
  static boolean pd(int l) {
      int sum = 0;
      for (int i = 1; i <= n; i++) {
          sum += (h[i] / l) * (w[i] / l);
          if (sum >= k) {
              return true;
          }
      }
      return false;
  }

  public static void main(String[] args) {

      Scanner in = new Scanner(System.in);
      n = in.nextInt();
      k = in.nextInt();
      //找到二分查找的上界
      int high = 0;

      for (int i = 1; i <= n; i++) {
          h[i] = in.nextInt();
          w[i] = in.nextInt();
          high = max(high, h[i]);
          high = max(high, w[i]);
      }

      // 二分下届由题意可得至少为1
      int low = 1;
      // 由于本题目就是求符合要求的Mid 值所以要将mid定义在二分查找外边
      int mid = 0;

      while (low < high) {
          mid = (low + high + 1) / 2;
          if (pd(mid))
              low = mid;
          else
              high = mid - 1;
          //        cout<<low<<" "<<high<<endl
      }
      //因为low=high所以输出哪一个都一样
      System.out.println(low);
  }
}

模板中的 <= 和 => 都可以换成其他判定条件，像上面根据题目分析即可。

M 次方根

题目描述:

小 A 最近在学高等数学，他发现了一道题，求$\sqrt[3]{27}$ 。现在已知，小 A 开始计算，$1$ 的三次方得$1$，$2$ 的三次方得$8$，$3$ 的三次方得$27$，然后他很高兴的填上了$3$。

接着他要求$\sqrt[5]{164}$ 。然后他开始$1$ 的三次方得$1$，$2$ 的三次方得$8$，$3$ 的三次方得$27$…

直到他算到了秃头，也没有找到答案。

这时一旁的小 B 看不下去了，说这题答案又不是个整数。小 A 震惊，原来如此。作为程序高手的小 A，打算设计一个程序用于求解 $M$ 次根下$N$的值。

但是由于要考虑精度范围，答案必须要保留 $7$ 位小数，连三次根号下$27$都要掰手指的小 A 又怎么会设计呢。请你帮小 A 设计一个程序用于求解 $M$ 次根号$N$。

数据范围：

$1 \leq N \leq 1e5$ $1 \leq M \leq 100$ 且 $M < N$

要求输入:

1
2
3
输入描述:

第一行输入整数 N 和 M，数据间用空格隔开。

要求输出：

1
输出描述: 输出一个整数，并保留 7 位小数。

样例:

1
2
3
4
5
6
7
输入样例：

27 3

输出样例：

3.000000

运行限制:

1
2
3
4
5
6
7
8
最大运行时间：1s
最大运行内存: 256M

注意：
1. 请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
2. 不要调用依赖于编译环境或操作系统的特殊函数。
3. 所有依赖的函数必须明确地在源文件中。
4. 不能通过工程设置而省略常用头文件。

题目分析

前面讲的都是整数二分，其实二分法还是可以用于实数。这个题目比较难，很多同学可能想不明白，想不明白就多读题，写写画画理解一下。这个题还有很多解法，现在告诉你了这道理用二分可以解答，请设计一个二分程序。

首先是这道题我们怎么下手：

根据前面的知识，我们要找到一个具有单调性的数列，去二分。这个题的关键是我们要去二分什么，这里可以二分的是 $a^M$ 中的 $a$，所以我们要先想办法设计出用于处理实数二分的代码。

这里给大家两个模板，都可以大家选择一个使用即可：

C++ 模版：

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
//模版一：实数域二分，设置eps法

//令 eps 为小于题目精度一个数即可。比如题目说保留4位小数，0.0001 这种的。那么 eps 就可以设置为五位小数的任意一个数 0.00001- 0.00009 等等都可以。

//一般为了保证精度我们选取精度/100 的那个小数，即设置 eps= 0.0001/100 =1e-6

while (l + eps < r)
{
    double mid = (l + r) / 2;

    if (pd(mid))
        r = mid;
    else
        l = mid;
}

//模版二：实数域二分，规定循环次数法
//通过循环一定次数达到精度要求，这个一般 log2N < 精度即可。N 为循环次数，在不超过时间复杂度的情况下，可以选择给 N 乘一个系数使得精度更高。

    for (int i = 0; i < 100; i++)
{

    double mid = (l + r) / 2;
    if (pd(mid))
        r = mid;
    else
        l = mid;
}

Python 模版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 实数域二分，设置eps法
# 令eps 为小于题目精度一个数即可，比如题目说保留4位小数，0.0001 这种的。那么eps 就可以设置为五位小数的任意一个数 0.00001- 0.00009 等等都可以。一般为了保证精度我们选取精度/100 的那个小数

eps = 1e-6
while l + eps < r:
  mid = (l + r) / 2
  if (pd(mid)):
      r = mid
  else:
      l = mid

# 实数域二分，规定循环次数法
# 通过循环一定次数达到精度要求，这个一般 log2N< 精度即可。N 为循环次数，在不超过时间复杂度的情况下，可以选择给N乘一个系数使得精度更高。

for _ in range(100):
  mid = (l + r) / 2
  if (pd(mid)):
      r = mid
  else:
      l = mid

Java 模版:

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
//令eps 为小于题目精度一个数即可。

//比如题目说保留4位小数，0.0001 这种的。那么eps 就可以设置为五位小数的任意一个数 0.00001- 0.00009 等等都可以。一般为了保证精度我们选取精度 /100 的那个小数，即设置  eps= 0.0001/100 =1e-6。

while (l + eps < r) {
    double mid = (l + r) / 2;

    if (pd(mid))
      r = mid;
  else
      l = mid;
}

// 实数域二分，规定循环次数法

//通过循环一定次数达到精度要求，这个一般log2N< 精度即可。N为循环次数，在不超过时间复杂度的情况下，可以选择给N乘一个系数使得精度更高。

for (int i = 0; i < 100; i++) {

    double mid = (l + r) / 2;
    if (pd(mid))
      r = mid;
  else
      l = mid;
}

模板讲完了，然后我们就要考虑判定条件了，怎样判定是否存在满足大于平均值的区间。当然这个题你可以使用语言中自带开方软件，但是我们还是联系一下实数的二分代码。

关于判定条件，我们应该设计一个代码用于比较 $a^m$ 和 $N$ 的大小关系。

在我们代码中：

1
2
3
4
if (pd(mid))
    r = mid;
else
    l = mid;

$pd$ 成功的情况，一定是 $pd$ 的 $mid$ 符合条件，且小于 $mid$ 的一定符合条件。因此我们要在大于 $mid$ 中继续查找，找到更大的 $mid$。

所以我们可以设计出如下判定条件:

1
2
3
4
5
6
7
8
9
10
11
12
13
double pd(double a,int m)
{
    double c=1;
    while(m>0)
    {
        c=c*a;
        m--;
    }
    if(c>=n)
        return true;
    else
        return false;
}

代码解答

C++ 实现：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <iostream>
#include<iomanip> //用于浮点数输出
using namespace std;

double n,l,r,mid;
double eps=1e-8;

bool pd(double a,int m)
{
    double c=1;
    while(m>0)
    {
        c=c*a;
        m--;
    }
    if(c>=n)
        return true;
    else
        return false;
}

int main()
{
    int m;
    cin>>n>>m;
//设置二分边界
    l=0,r=n;
//实数二分
    while (l + eps < r)
    {
        double mid = (l + r) / 2;
        if (pd(mid,m))
            r = mid;
        else
            l = mid;
    }

    cout<<fixed<<setprecision(7)<<l;
    //一般使用print
    //printf("%x.yf",n)
    //其中X是固定整数长度，小数点前的整数位数不够，会在前面补0
    //y是保留小数位数，不够补零
    //printf("%.7f",l);
    return 0;
}

查找上界这里可以直接输入的时候查询，这道题实际上是可以少次操作的，代码如下。

Python 实现

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
29
30
31
32
33
34
35
36
37
n = 0.0
m = 0
l = 0.0
r = 0.0
mid = 0.0
eps = 0.00000001

def pd(a, m):
  c = 1.0
  cnt = int(m)

  while cnt > 0:
      c = c * a
      cnt -= 1

  if c >= n:
      return True

  else:
      return False


if __name__ == '__main__':

  n, m = input().split()

  l = 0
  r=n=int(n)

  while l + eps < r:
      mid = (l + r) / 2
      if (pd(mid, m)):
          r = mid
      else:
          l = mid

print("%.7f" % l)

Java 实现

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package com.company;
import java.util.Scanner;

public class Main {

  static double n, l, r, mid;
  static double eps = 1e-8;

  static boolean pd(double a, int m) {
      double c = 1;
      while (m > 0) {
          c = c * a;
          m--;
      }

      if (c >= n)
          return true;
      else
          return false;
  }

  public static void main(String[] args) {

      int m;
      Scanner in =new Scanner(System.in);
      n=in.nextDouble();
      m=in.nextInt();
//设置二分边界
      l = 0;
      r = n;
//实数二分
      while (l + eps < r) {
          double mid = (l + r) / 2;
          if (pd(mid, m))
              r = mid;
          else
              l = mid;
      }
      System.out.println(String.format("%.7f",l));
  /*
   关于string.format 的应用

  double num = 123.4567899;
  System.out.print(String.format("%f %n", num)); // 123.456790
  System.out.print(String.format("%a %n", num)); // 0x1.edd3c0bb46929p6
  System.out.print(String.format("%g %n", num)); // 123.457

  可用标识：

        -，在最小宽度内左对齐,不可以与0标识一起使用。
        0，若内容长度不足最小宽度，则在左边用0来填充。
        #，对8进制和16进制，8进制前添加一个0,16进制前添加0x。
        +，结果总包含一个+或-号。
        空格，正数前加空格，负数前加-号。
        ,，只用与十进制，每3位数字间用,分隔。
        (，若结果为负数，则用括号括住，且不显示符号。

  可用转换符：

        b，布尔类型，只要实参为非false的布尔类型，均格式化为字符串true，否则为字符串false。
        n，平台独立的换行符, 也可通过System.getProperty("line.separator")获取。
        f，浮点数型（十进制）。显示9位有效数字，且会进行四舍五入。如99.99。
        a，浮点数型（十六进制）。
        e，指数类型。如9.38e+5。
        g，浮点数型（比%f，%a长度短些，显示6位有效数字，且会进行四舍五入）

   */

  }
}

总结

二分的题目主要是必须要求是单调的，一般会有条件等字眼。做这种题目主要还是找到递增或者递减的序列，然后关于序列的判定条件。或者通过观察时间复杂度来看是否可以使用二分，二分法的题目相对来说比较明显，设计起来也比较简单，模板不用死记硬背，理解一下，很快就可以独立写出来。

≡