二分搜索算法专题(挑战程序设计竞赛)

桃扇骨 2022-12-28 12:45 180阅读 0赞

### 文章目录 ###

*  二分搜索算法的四大应用
 *   *  一、从有序数组中查找某个值
     *   *  例题：
         *   *  代码：
     *  二、假定一个解并判断是否可行
     *   *  例题：
         *   *  题目描述
             *  输入描述
             *  输出描述
             *  输入
             *  输出
             *  解题思路
             *  代码：
     *  三、最大化最小值
     *   *  例题：
         *   *  题目描述
             *  输入描述
             *  输出描述
             *  输入
             *  输出
             *  提示
             *  算法分析
             *  代码：
     *  四、最大化平均值
     *   *  例题：
         *   *  算法分析
             *  代码：
     *  关于二分精度的总结

--------------------

# 二分搜索算法的四大应用 #

二分搜索法，是通过不断缩小解可能存在的范围，从而求得问题最优解的方法。

## 一、从有序数组中查找某个值 ##

这是二分搜索最常规的操作，在一个有序的数组中查找某个值

### 例题： ###

![1-1][]

#### 代码： ####

//输入
    int n, k;
    int a[MAX_N];
    
    void solve()
    {
        
      //初始化解的存在范围
    	int lb = -1, ub = n;
      
      //重复循环，直到解的存在范围不大于1
      while(ub - lb > 1){
        
        int mid = (lb + ub) / 2;
        if(a[mid] >= k){
        
          //如果mid满足条件，则解的存在范围变为(lb,mid]
          ub = mid;
        }else{
        
    			//如果mid不满足条件，则解的存在范围变为(mid,ub]
          lb = mid;
        }
      }
      
      //这时，lb + 1 = ub
      printf("%d\n", ub);
    }

## 二、假定一个解并判断是否可行 ##

给定一个需要的条件，根据条件二分遍历满足条件的解。

**假定一个解，再去判断这个解是否可行，再不断缩小范围**

### 例题： ###

#### 题目描述 ####

为了购买网络线缆，评委会联系了当地的网络解决方案提供商，要求为他们出售一定数量的等长度的线缆。评审委员会希望电报越长越好，让参赛者坐得越远越好。

公司的电缆主管被派去执行这项任务。他知道库存中每根电缆的长度，最多是一厘米，他可以精确地切割每根电缆，并被告知必须切割的部分的长度。然而，这一次，长度不知道和电缆主人完全困惑。

你要帮助电缆主，通过编写一个程序，将确定最大可能长度的电缆片可以从电缆切断的股票，以获得指定的数量。

#### 输入描述 ####

输入文件的第一行包含两个用空格分隔的整数**N**和**K**。\*\*N (1 <= N <= 10000)\*\*是库存电缆的数量，\*\*K (1 <= K <= 10000)\*\*是请求的数量。第一行后面是N行，每行有一个数字，表示库存中每根电缆的长度(以米为单位)。所有的电缆都至少1米长，最多100公里长。输入文件中的所有长度都以厘米精度写入，小数点后正好有两位数字。

#### 输出描述 ####

写入输出文件的最大长度(米)，电缆主可以削减从电缆的股票，以获得要求的件数。数字的书写精度必须为厘米，小数点后必须有两位数字。

如果无法将所请求的片段数量(每个片段至少有1厘米长)分割，则输出文件必须包含单个数字“0.00”(不带引号)。

#### 输入 ####

> 4 11  
> 8.02  
> 7.43  
> 4.57  
> 5.39

#### 输出 ####

> 2.00

#### 解题思路 ####

![2-11][]

#### 代码： ####

int N,K;
    double L[MAX_N];
    
    //判断是否满足条件
    bool C(double x)
    {
        
      //以x为长度来切割绳子
      //如果切割的绳子数超过K，就说明该长度可行
      int num = 0;
      for(int i = 0; i < N; i++){
        
    		num += (int)(L[i] / x);
      }
      return num >= K;
    }
    
    void solve()
    {
        
    	//初始化解的范围
      double lb = 0, ub = INF;
      
      //重复循环，直到解的范围足够小
      //100的循环是为了控制精度，使精度达到10^-30的精度范围
      for(int i = 0; i < 100; i++){
        
        double mid = (lb + ub) / 2;
        if(C(mid))
          lb = mid;
        else
          ub = mid;
      }
      
      printf("%.2f\n", floor(ub * 100) / 100);
    }

## 三、最大化最小值 ##

通过二分法也可以很好的解决最大化最小值的问题

### 例题： ###

#### 题目描述 ####

农民约翰建了一个新的长谷仓，有**N**个摊位。摊位位于**x1、…，xN (0 <= xi <= 1,000,000,000)。**

他的\*\*C (2 <= C <= N)\*\*头奶牛不喜欢这种谷仓布局，一旦被关进牛栏，它们就会变得咄咄逼人。为了防止奶牛互相伤害，FJ想要将奶牛分配到牛棚中，使它们之间的最小距离尽可能的大。最大最小距离是多少?

#### 输入描述 ####

*  第1行：两个用空格分隔的整数：**N和C**
 *  第 2…N+1行： 第i+1行包含一个整数摊位位置，**xi**

#### 输出描述 ####

*  第1行：一个整数：最大最小距离

#### 输入 ####

> 5 3  
> 1  
> 2  
> 8  
> 4  
> 9

#### 输出 ####

> 3

#### 提示 ####

> FJ可以把他的3头奶牛放在1号、4号和8号位置的牛栏里，这样就能保证3只奶牛之间的最小距离。
> 
> 庞大的输入数据，建议使用scanf。

#### 算法分析 ####

![3-11][]

#### 代码： ####

//输入
    int N,M;
    int x[MAX_N];
    
    //判断是否满足条件
    bool C(int d)
    {
        
      int last = 0;
      for(int i = 1; i < M; i++){
        
        int crt = last + 1;
        //保证任意两个牛之间的距离不超过d
        while(crt < N && x[crt] - x[last] < d) 
          crt++;
        if(crt == N)
          return false;
        last = crt;
      }
      return true;
    }
    
    void solve()
    {
        
      //最开始时对x数组排序
      sort(x, x + N);
      
      //初始化解的存在范围
      int lb = 0, ub = INF;
      
      while(ub - lb > 1){
        	//保证精度为整数
        int mid = (lb + ub) / 2;
        if(C(mid))
          lb = mid;
        else
          ub = mid;
      }
      
      printf("%d\n", lb);
    }

## 四、最大化平均值 ##

### 例题： ###

![4-1][]

#### 算法分析 ####

![4-2][]

#### 代码： ####

//输入
    int n,k;
    int w[MAX_N], v[MAX_N];
    
    double y[MAX_N];	// v - x * w
    
    //判断是否满足条件
    bool C(double x)
    {
        
      //计算权重v - x * w
      for(int i = 0; i < n; i++)
        y[i] = v[i] - x * w[i];
      sort(y, y + n);
      
      //计算y数组中从大到小前k个数的和
      double sum = 0;
      for(int i = 0; i < k; i++)
        sum += y[n - i - 1];
     	
      return sum >= 0;
    }
    
    void solve()
    {
        
      double lb = 0, ub = INF;
      for(int i = 0; i < 100; i++){
        
        double mid = (lb + ub) / 2;
        if(C(mid))
          lb = mid;
        else
          ub = mid;
      }
      
      printf("%.2f\n", ub);
    }

## 关于二分精度的总结 ##

1、**可以通过控制二分循环来控制二分精度**，可以将终止条件设置为100次的循环，那么精度就可以达到10\-30的精度范围，同样也可以把终止条件设为 `(ub - lb) > EPS` 这样，**但是注意，如果EPS取得太小，就有可能因为浮点小数精度的原因导致陷入死循环**

[1-1]: /images/20221120/f134ae6fc67846af9046aad8ea025cdd.png
[2-11]: /images/20221120/d7421c7f28a54cdc84eff2078a9ecdc1.png
[3-11]: https://s1.ax1x.com/2020/03/17/8aQDqP.jpg
[4-1]: https://s1.ax1x.com/2020/03/17/8aQdxA.jpg
[4-2]: https://s1.ax1x.com/2020/03/17/8aQ0KI.jpg