二分查找

二分查找又叫折半查找,需要注意的是二分查找需要数列是有序的,如果查找到需要的数,返回所在位置
,否则返回NULL。

如一个升序长度为7的数组a[7]，分别为1，2，3，4，5，6，7，如下图:
数组序列
如果查找大小为5的值所在的位置，过程如下：
首先设置两个变量，分别为left = 0，right = 6，left这个参数表示左边端点，right表示右边端点，
因为数组的下表是从0开始的，所以right = 6。
步骤一
然后开始查找，查找left，right的平均值mid，即mid=(left + right)/2,然后把a[mid]与需要查找
的值5比较，若a[mid] < 5，则太小了，修改left的值，让left = mid + 1；若a[mid] >　5,则表明
查找的数值过大，这是right = mid - 1；若a[mid] = 5，则说明此时的mid即使5在数组中的位置。
所以第一次查找的mid =(0+6)/2= 3,a[mid] = a[3] = 4 < 5,更新left = mid+1。此时left和right
的位置如下图所示：
步骤二
第二次查找mid=(4+6)/2=5,a[mid]=a[5]=6 > 5,更新right = mid - 1。更新后的left和
right如下图所示：
步骤三
第三次查找mid=(4+4)/2=4,a[mid]=a[4]=5,与查找值相等,停止查找,返回位置4。

实战演练

进击的奶牛

题目描述

Farmer John 建造了一个有 N（2<=N<=10 ^ 5) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是
x1, x2,… xN（0<=xi<=10 ^ 9）。

他的 C（2<=C<=N）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的
互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，
这个最大的最近距离是多少呢？

输入格式

第 1 行：两个用空格隔开的数字 N 和 C。

第 2 ~ N+1 行：每行一个整数，表示每个隔间的坐标。

思路：

从题目就可以看的出来这是一个明显的二分问题，我们只需要处理每个每个牛所在的位置与前一个牛的位置距离
差是否满足某个条件，这里需要满足a[i+1] - a[i] >= mid,如果满足这样的个数大于等于C，我们就认为
此时的距离mid可以实现，那样就要增大mid，即向右区间移动，left = mid + 1，不满足则减小mid的值，
向左区间移动，即right=mid-1。最后比较每次的mid求得最大值。代码如下：

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
#include <bits/stdc++.h>
using namespace std;
int n,m;
int ans=-1;
int a[1000005];
bool check(int x){   //答案是否满足，满足返回1，反之返回0
    int now = 1, num = 1;
    for (int i = 2; i <= n; i++){
        if (a[i]-a[now]>=x){
            now=i;
            num++;
        }
    }
    return num>=m;
}
void merge(int l,int r){
	if(r-l<0) return;    //边界
	int mid=l+(r-l)/2;    //这样处理防止溢出
	if(check(mid)){   //如果满足，我们记录当前最大值，然后往右区间寻找答案
		merge(mid+1,r);
		ans=max(ans,mid);
	}
	else{  //如果不满足，就往左区间寻找
		merge(l,mid-1);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);  //输入是无序的，要排序处理。
	merge(1,a[n]-a[1]);
	cout<<ans;
    return 0;
}

紧接着，我们再来看另一题：

砍树

题目描述

伐木工人 Mirko 需要砍 M 米长的木材。对 Mirko 来说这是很简单的工作， 因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。
不过，Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，
并锯掉所有树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为
20,15,10 和 17，Mirko 把锯片升到 15 米的高度，切割后树木剩下的高度将是 15,15,10 和 15，而 Mirko 将从第 1 棵树得到 5 米，
从第 4 棵树得到 2米，共得到7米木材。

Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度H，
使得他能得到的木材至少为M米。换句话说，如果再升高 1 米，他将得不到 M 米木材。

输入格式

第 1 行 2 个整数 N 和 M，N 表示树木的数量，M 表示需要的木材总长度。

第 2 行 N 个整数表示每棵树的高度。

输出格式

1 个整数，表示锯片的最高高度。

思路：

和其他二分思路一样，这里的mid代表高度，让最低的高度为1，最高的高度为树的最大高度，每次循环判断，如果得到的树木长度大于M，
则向上继续移动，left = mid + 1；反之，right=mid-1。

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
#include <bits/stdc++.h>
using namespace std;
int n,m,l,r;
int a[1000005];
bool check(int x){   //答案是否满足，满足返回1，反之返回0
    long long int num=0;
    for (int i = 1; i <= n; i++){
        num += max(0,a[i] - x);
    }
    return num>=m;
}
void merge(){
	if(r-l<0) return;    //边界
	int mid=l+(r-l)/2;    //这样处理防止溢出
	if(check(mid)){   //如果满足，我们记录当前最大值，然后往右区间寻找答案
        l = mid +1;
		merge();
	}
	else{  //如果不满足，就往左区间寻找
        r = mid - 1;
		merge();
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
        r = max(r,a[i]);
	}
    l=0;
	merge();
	cout<<r;
    return 0;
}

关于二分查找的问题，就到这里，如果存在问题，请与我联系！