（3）二分查找

目录

（3）二分查找

主要分类

基本思想

1、整数二分

二分本质

实现步骤

模板

复杂度

接下来是实战演练！！！

2、浮点数二分

练习：开平方

优化改进

总结

写在最后！！！

二分查找也称折半查找（Binary Search）。它是一种效率较高的查找方法。但是，二分查找要求线性表必须采用顺序存储结构，且表中元素要按照关键字有序排列，注意必须要是有序排列。

主要分类

二分查找主要分为两大类：整数二分和浮点数二分

 （PS：在这里主要介绍整数二分）

基本思想

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与mid做比较，如果x=a[n/2]，则找到x算法中止；如果x<a[n/2]，则只要在数组a的左半部分继续搜索x，如果x>a[n/2]，则只要在数组a的右半部搜索x。（百度）

在这里，假设x在闭区间[left,right]中，每次将区间长度缩小一半，当left=right时，我们就找到了x。

1、整数二分

二分本质

假设给定某一闭区间，在这区间上我们定义了某种性质，使得整个区间一分为二，在区间的右半边是满足其性质的，左半边是不满足其性质的（因为是整数二分，所有左右半边没有交点），那么使用二分可以寻找性质的边界，既可以寻找满足性质的边界点，也可以寻找不满足性质的边界点，那么这便是二分的本质。（如下图）

实现步骤

 根据上图：

1、二分查找出“不满足性质”区间（左半部分）的边界

1. 找出中间值：mid = (left+right+1)/2
2. 编写check()函数，if判断mid是否满足其性质：若满足（为true）：则答案在[mid,right]区间；若不满足（为false）:则答案在[left,mid-1]区间；

2、二分查找出“满足性质”区间（右半部分）的边界

1. 找出中间值：mid = (left+right)/2
2. 编写check()函数，if判断mid是否满足其性质：若满足（为true）：则答案在[left,mid]区间；若不满足（为false）:则答案在[mid+1,right]区间；

问题：为什么 mid=(left+right+1)/2 中 要 “+1” ？

答：因为是向下取整，当 left=right-1 时，如果补不上“+1”，在向下取整的条件下，mid=left，如果当在查询时，正好满足性质（为true），则答案仍然在[left,right]区间，相当于，我们循环了一遍，但区间没有改变，就进入了死循环。

模板

//区间[left,right]被划分为[left,mid]和[mid+1,right]时使用
int p1(int left,int right)
{
	while(left < right)
	{
		int mid = left + right >> 1; 
		//check()判断mid是否满足性质 
		if(check(mid)) right = mid; 
		else left = mid + 1;
	}
	return 1;
} 
int p2(int left,int right)
{
	while(left < right)
	{
		int mid = left + right+1 >> 1; 
		if(check(mid)) left = mid;
		else right = mid - 1;
	}
	return 1;
} 

复杂度

平均时间复杂度：O(log2n)

空间复杂度：O(1)

接下来是实战演练！！！

题目：

 代码：

#include <iostream>
using namespace std;

const int N = 100010;
int n,m;
int q[N]; 

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 0; i < n; i++)
	{
		scanf("%d",&q[i]);
	}
	
	while(m--)
	{
		int x;
		scanf("%d",&x);
		
		int left = 0,right = n - 1; //定义边界 
		
		while(left < right)
		{
			int mid = left + right >> 1; //注意 
			if(q[mid] >= x) right = mid; //注意 
			else left = mid + 1;
		}
		
		if(q[left] != x) cout << "-1 -1" << endl;
		else
		{
			cout << left <<' ';	
				
			int left = 0,right = n -1;
			while(left < right)
			{
				int mid = left + right + 1 >> 1; //注意
				if(q[mid] <= x) left = mid; //注意
				else right = mid -1;
			}
			cout << left << endl;
		}
	}
	return 0;
}

 结果：

2、浮点数二分

浮点数二分相对简单，因为没有整除，所以区间可以严格的分成两部分，不需要考虑边界问题。至于其他则与整数二分思想一致，但要时刻保证所求的数在区间内部。当right-left长度足够小时，则认为找到x。

练习：开平方

代码：

#include <iostream>
using namespace std;

int main()
{
	double x;
	cin >> x;
	double left = 0,right = x; //区间[0,x] 
	
	while(right - left > 1e-8 ) //精度表示，也可以迭代 ，直接循环比较多的次数 
	{
		double mid = (left + right)/2;
		if(mid * mid >= x) right = mid;
		else left = mid;	
	}
	printf("%lf\n",left); //保留6位小数 
	return 0;
}

 结果：

优化改进

根据二分查找，有人给出了更精准的计算方式，即要查找位置 p=left+(x-a[left])/(a[right]-a[left])×(right-left)，这种计算方式是为了找 key 所在的相对位置，让 x 的值更接近划分的位置，从而减少了比较的次数。
这种对二分查找的优化叫插值查找，插值查找对于比较大并且比较均匀的数列来说，性能会好很多；但是如果数列极不均匀，插值查找未必会比二分查找的性能好。

总结

1、二分查找适用于已经有序的序列。比如猜数字游戏，采用二分查找要比普通查找要效率快得多，但是强调是有序。但也有一种特殊情况可以不必有序序列，如商品选取（从一堆标准商品中查找唯一次品）也可以使用二分进行查找。

2、二分的本质并不是单调性，即有单调性的一定可以二分，但是无单调性的也可以二分，他与边界有关！

写在最后！！！

这是视频学习笔记，但是作为算法小白，知识还很不牢固。如果有错误请欢迎指正~~，感谢！！！