二分查找

一、什么时候可以使用二分查找

二分查找用于在有序数组中快速查找。

如果数组还没有排序，需要先排序：

sort(a+1,a+1+n);

每次检查中间位置，就能排除一半范围，因此速度很快。

二、二分查找的基本过程

查找范围是 [l,r]：

int l=1,r=n;
while(l<=r){
	int mid=(l+r)/2;
}

比较 a[mid] 和 x：

• a[mid]<x：目标只能在右边，l=mid+1
• a[mid]>x：目标只能在左边，r=mid-1
• a[mid]==x：说明找到了

注意：移动的是 mid+1 或 mid-1，不能仍然保留 mid。

三、判断数字是否出现

bool bs(int x){
	int l=1,r=n;
	while(l<=r){
		int mid=(l+r)/2;
		if(a[mid]==x) return 1;
		if(a[mid]<x) l=mid+1;
		else r=mid-1;
	}
	return 0;
}

这种问题找到答案后可以立即返回。

四、查找第一个或最后一个位置

遇到“第一个”或“最后一个”时，找到一个符合要求的位置还不能结束。

• 找第一个：记录答案后继续向左找
• 找最后一个：记录答案后继续向右找
• 没有符合要求的位置：返回 -1

查找 x 第一次出现的位置

int bs2(int x){
	int l=1,r=n,ans=-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(a[mid]==x){
			ans=mid;
			r=mid-1;//继续向左找
		}
		else if(a[mid]<x) l=mid+1;
		else r=mid-1;
	}
	return ans;
}

查找大于 x 的第一个位置

int bs4(int x){
	int l=1,r=n,ans=-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(a[mid]>x){
			ans=mid;
			r=mid-1;//符合要求，继续向左找
		}
		else l=mid+1;
	}
	return ans;
}

五、七种常见查找

记忆方法：

• “第一个”符合要求的位置：向左找
• “最后一个”符合要求的位置：向右找
• 是否包含等于：看题目中有没有“等于”

六、例子

有序数组：

1 2 2 2 5 8

查找 x=2：

七、检查清单

写完二分查找后依次检查：

1. 数组是否已经有序。
2. 初始范围是否为 l=1,r=n。
3. 循环条件是否为 l<=r。
4. a[mid]<x 时是否写成 l=mid+1。
5. a[mid]>x 时是否写成 r=mid-1。
6. 找边界时是否定义了 ans=-1。
7. 找到后应该继续向左还是向右。
8. 条件中的 <、<=、>、>= 是否符合题意。