[数据结构与算法]二分查找（只记一个模板）

注意：
数组元素都是从下标1开始的。

计蒜客二分查找之例题1

——查询整数 x 是否在数组 A 中，存在，输出YES；不存在，输出NO

//tmp所指的为下标，范围[1,n]
int B_S(int x)
{
	int low=1,high=n,tmp=low,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(a[mid]<=x)
		{
			tmp=mid;
			low=mid+1;
		}
		else
			high=mid-1;
	}
	if(a[tmp]!=x)	return 0;
	else			return 1;
}

计蒜客二分查找之例题2

——询问在数组 A 中，大于等于 x 的最小值，如果存在，输出该值，不存在输出-1。

//tmp指向第一次大于等于 x 的下标
//等同于 p1=lower_bound(a+1,a+1+n,x)-a;
//tmp和p1的指向可能存在不同，少一个特判：if(a[tmp]<x) tmp=n+1;
//当查询的 x 大于数组内所有元素，p1和tmp需指向n+1
int B_S(int x)
{
	int low=1,high=n,tmp=low,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(a[mid]>=x)
		{
			tmp=mid;
			high=mid-1;
		}
		else
			low=mid+1;
	}
	//tmp最初指向可能不变，加一个特判 
	if(a[tmp]>=x)	return a[tmp];
	else			return -1;
}

计蒜客二分查找之例题3

——题意：查询在数组 A 中，比 x 大的最小值，存在就输出该值，不存在，输出-1

//tmp指向第一个大于 x 的下标
//p2=upper_bound(a+1,a+1+n,x)-a;
//tmp和p1的指向可能存在不同，少一个特判：if(a[tmp]<=x) tmp=n+1;
//当查询的 x 大于数组内所有元素，p1和tmp需指向n+1
int B_S(int x)
{
	int low=1,high=n,tmp=low,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(a[mid]>x)
		{
			tmp=mid;
			high=mid-1;
		}
		else
			low=mid+1;
	}
	//tmp可能不变，加一个特判 
	if(a[tmp]>x)	return a[tmp];
	else			return -1;
}

计蒜客二分查找之例题4

——题意：查询在数组 A 中，等于 x 的数字有多少个
——思路：两次查询，例题3 - 例题2。对于特判哪里需要改一改。

计蒜客二分查找之例题5

——题意：询问在数组 A 中，小于等于 x 的最大值，存在返回其值，不存在返回 -1 。
——代码：第一个代码就是。 tmp指向最后一次小于等于 x 的下标

计蒜客二分查找之例题6

——题意：询问在数组 A 中，小于 x 的最大值，存在返回其值，不存在返回 -1 。
——代码：第一个代码去掉等于号，tmp指向最后一次小于 x 的下标

提高题之天梯赛三足鼎立

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110000;
int a[N];
int main()
{
	int i,n,aa,bb,he,cha,p1,p2;
	scanf("%d %d",&n,&aa);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	ll ans=0; 
	for(i=1;i<=n;i++)
	{
		bb=a[i];
		he=aa+bb;
		cha=abs(aa-bb);
		//第三边需满足的条件
		//小于其它两边之和，大于其它两边之差
		p1=lower_bound(a+1+i,a+1+n,he)-a;//返回第一个>=和的数的下标
		p2=upper_bound(a+1+i,a+1+n,cha)-a;//返回第一个>差的数的下标
		ans+=(p1-p2);
	}
	printf("%lld\n",ans);
	return 0;
}