算法竞赛--二分(一)

二分查找

二分查找是基于有序序列的查找算法,该算法一开始令[low,high]为整个区间的下标区间，然后每次测试当前[left,high]的中间位置mid=(low+high)/2,判断A[mid]与欲查询的元素n的大小。

参考代码如下:

#include<stdio.h>
int main()
{
	int n;
	while(scanf("%d",&n)==1)
	{
		int A[10]={3,7,8,11,15,21,33,52,66,88};
		int low=0,high=9,k=-1;
		while(low<=high)
		{
			int mid=(low+high)/2;
			if(A[mid]==n)
			{
				k=mid;
				break;;
			}
			else if(A[mid]>n)
				high=mid-1;
			else
				low=mid+1;	 
		}
		printf("%d\n",k);
	}
	return 0;
}

求序列中第一个大于等于x的元素的位置L。

思路:如果A[mid]>=x,则要求的位置一定在mid处或者mid左侧,令high=mid,否则一定在mid右侧,令low=mid+1;

注意:循环条件为low<high,low=high时跳出循环，刚好夹出唯一的位置，就是需要的结果.

参考代码如下:

#include <stdio.h>
int main()
{
	int A[5]={1,3,3,3,6},n;
	while(scanf("%d",&n)==1)
	{	
		int low=0,high=5;
		while(low<high)
		{
			int mid=(low+high)/2;
			if(A[mid]>=n)
				high=mid;
			else
				low=mid+1;
		}
		printf("L=%d\n",low);
	}
	return 0;
}

求序列中第一个大于x的元素的位置

思路:如果A[mid]>x,则要求的位置一定在mid处或者mid左侧,令high=mid,否则一定在mid右侧,令low=mid+1;

#include <stdio.h>
int main()
{
	int n;
	int A[5]={1,3,3,3,6};
	while(scanf("%d",&n)==1)
	{
		int low=0,high=5;
		while(low<high)
		{
			int mid=(low+high)/2;
			if(A[mid]>n)
				high=mid;
			else
				low=mid+1;
		}
		printf("R=%d\n",high);
	}
	return 0;
}

模板:寻找第一个满足某条件的元素的位置(如果寻找最后一个满足条件C的，可以寻找第一个满足条件!C的，然后将该位置减1)

左闭右闭[low,higjh]

while(low<high)
{
	int mid=(low+high)/2;
	if(条件成立)
		high=mid;
	else
		low=mid+1;
}
return low;

左开右闭(low,high)

while(low+1<high)
{
	int mid=(low+high)/2;
	if(条件成立)
		high=mid;
	else
		low=mid;
}
return right;