发表于 更新于

二刷二分查找

​ 第一次接触二分查找还是在大一刚开学的时候，当时懵懵懂懂地进了新生赛的群，看着一个又一个算法，心中油然起一股子干劲，一定要把这些算法全部都刷完。

​ 当时对于二分查找中的开闭区间，左右边界能否相等之类的问题琢磨的并不透，因此我觉得很有二刷的必要性

​ 首先就是四种情况：左闭右闭、左闭右开、左开右闭、左开右开。当然，常用的还是左闭右闭以及左闭右开。

废话不多说，直接上两个板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Binart_search(int x){//左闭右闭 
	int l=1,r=n,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(a[mid]>x)r=mid-1;	
		else if(a[mid]<x)l=mid+1;
		else return mid;
	}
	return -1;
}
int Binart_search(int x){//左闭右开 
	int l=1,r=n,mid;
	while(l<r){
		mid=(l+r)/2;
		if(a[mid]>x)r=mid;	
		else if(a[mid]<x)l=mid+1;
		else return mid;
	}
	return -1;
}

值得注意的有以下几点：

  1. while中的左边界和右边界，我们需要满足一个合法的区间，因此，左右边界也必须与数组的开闭形式一致。
  2. 更新后的值。当左闭右闭时，由于a[mid]本身存在与我们需要查找的范围中，又因为我们要找的值小于或者大于该a[mid]，因此在下一次判断中我们就不需要再加上这个a[mid]了。故r=mid-1;l=mid+1。当左闭右开时，同理。
  3. mid相加溢出问题，如果l和r两个都为非常大的数字，那么相加后必定也非常大，这里我们就需要用到数学知识，将mid=(l+r)/2改为mid=l+(r-l)/2，这两个式子是等效的，显然，l-r相比l+r安全多了。

如果数组中出现了很多相同的数字，即非严格单调数组，那么我们可以这么改进。

1
2
3
4
5
6
7
8
9
10
int Binart_search(int x){//左闭右闭 
	int l=1,r=n,mid;
	while(l<=r){
		mid=l+(r-l)/2;
		if(a[mid]<x)l=mid+1;
		else r=mid-1;
	}
    if(a[l]!=x)return -1;
	return l;
}

这里我们将三个判断改为两个判断，即当a[mid]<=x都会更新边界，这样我们就可以排除重复的元素，因此来寻找某个元素第一次出现的位置。同样，如果我们像知道某个元素最后一次出现的位置，那么只要将l和r的逻辑位置交换一下即可。