整数二分查找的实现

引入

        在一个有序数组中，如果我们想查找某一元素，朴素做法就是从前往后枚举，时间复杂度会达到。但是因为此数组是有序的，所以就可以通过这个性质，使用二分查找实现，可以使时间复杂度降到。

        下面我们就来讲整数二分查找的实现。

定义

        二分查找（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是用来在一个有序数组中查找某一元素的算法。

过程

        整数二分查找的思路是这样的：假设目标值在闭区间中， 每次将区间长度缩小一半，当时，我们就找到了目标值。

        以在一个升序数组中查找一个数为例。

        它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

        我们通常想到二分查找就会想到单调性，认为二分查找只能用于具有单调性的题目。其实不然，只要一个题目具有二段性，二分查找就有用武之地。

Q：什么是单调性呢？

A：单调性通俗点说，就是元素有序，即一个升序或降序的数组。

Q：那什么又是二段性呢？

A：二段性是指对某一范围内的数据，存在一个临界点，使得临界点某一侧的所有数据都满足某一性质，另一侧的所有数据都不满足这一性质，就称这一范围内的数据具有二段性。

        我们可以从中看出，二分查找的本质不在于单调性，而是二段性！

        其实，整数二分查找比浮点数二分查找要复杂得多，浮点数二分查找无需考虑边界，而整数二分查找在代码实现上还要判断加1减1。

        所以，整数二分查找如果写之前不考虑好想要查找的是什么，十有八九会是死循环或者查找错误，就算侥幸写对了也只是运气好而已！

性质

        时间复杂度

        二分查找的平均与坏时间复杂度均为，最优时间复杂度为。

        空间复杂度

        二分查找的空间复杂度为（迭代版本）。

代码

        下面给出两种整数二分查找函数的实现：

bool check(int x){

}

int bsearch_1(int l,int r){
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))
			r=mid;
		else
			l=mid+1;
	}
	return l;
}

int bsearch_2(int l,int r){
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid))
			l=mid;
		else
			r=mid-1;
	}
	return l;
}

        代码解释

        check()函数的作用是检查x是否满足某种性质；bsearch_1()函数的作用是区间[l,r]被划分成[l,mid]和[mid+1,r]时使用（即查找左边界）；bsearch_2()函数的作用是区间[l,r]被划分成[l,mid-1]和[mid,r]时使用（即查找右边界）。

        两种整数二分查找函数的区别

        这两种整数二分查找函数有什么区别呢？

        第一种（bsearch_1），查找左边界：当我们将区间划分成和时，其更新操作是或者，计算时不需要加。

        第二种（bsearch_2），查找右边界：当我们将区间划分成和时，其更新操作是或者，计算时需要加。

        注意，两种整数二分查找中的加1减1不要搞混了，什么时候加，什么时候减，什么时候不写要明确，不然会产生死循环！

        两种整数二分查找函数的应用

        例如数组1 2 2 3 3 3 4，如果你想查找数组中的第一个3（红色），就需要用第一种二分查找（查找左边界）；如果你想查找数组中的最后一个3（绿色），就需要用第二种二分查找（查找右边界）。

上一篇-求逆序对问题的实现    C++算法基础专栏文章    下一篇-浮点数二分查找的实现

每周六更新一篇文章，内容一般是自己总结的经验或是在其他网站上整理的优质内容

点个赞，关注一下呗~