二分查找

注：本文来源于网络修改加自我看法，如有不足之处可在下方进行评论补充，感谢支持！

二分查找，你可能听不懂，说人话就是也就是我们常说的「对半查找法」

举个例子：A和B玩猜数游戏，B想了一个1到100之间的数，不告诉A，A第一次猜50，B说猜小了，A又猜75，B说猜小了，A猜87，B说猜大了，A猜85，B说猜对了。

这就是二分查找，理论上，二分查找的时长会是正常一个一个数找快50%。

段落引用在用二分法进行查找时，==查找对象的数组必须是有序的==，即各数组元素的次序是按其值的大小顺序存储的。

其基本思路就是：先确定待查数据的范围（常用 [left,right] 来表示），然后逐步缩小范围直到找到或找不到该记录为止。

具体的做法（可拖动下方小条来移动）：先取数组中间位置（mid=(left+right)/2）的数据元素与给定值比较。若相等，则查找成功；否则，若给定值比该数据元素的值小（或大），则给定值必在数组的前半部分[left,mid-1]（或后半部分[mid+1,right]），然后在新的查找范围内进行同样的查找。如此反复进行，直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。因此，二分查找每查找一次，或成功，或使查找数组中元素的个数减少一半，当查找数组中不再有数据元素时，查找失败。

我知道你看不懂，我们直接上道例题看代码。

题目（来源于网络）：

有若干个数按由小到大的顺序存放在一个一维数组中，输入一个数x，用二分查找法找出x是数组中第几个数组元素的值。如果x不在数组中，则输出“无此数！”。

我们读题，已知：要用二分查找去找一个数组其中的一个数据，没有这个数据就输出“无此数！”。

可以看出，题目不难，大家可以思考一下。

我在这里提供一个编程思路：

设有一数组a[n]，数组中的元素按值从小到大排列有序。用变量low、high和mid分别指示待查找元素所在区间的下界、上界和中间位置。初始时，low=0，high=n-1。

好，题目不难。我就直接上代码了：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
/*
等待：_sleep(多少秒*1000);
	*/
using namespace std;

int main(){
	const int n=5;
	int a[n]={1,9,1,6,7}; 
	int x,low,high,mid;
	cout<<"要找哪个数？";
	cin>>x;//这里输入的是要找x这个数有没有
	low=0; high=n-1;//这里是初始化区间，也有叫格式化区间
	while(low<=high){
		mid=(low+high)/2;
		if(x==a[mid]){
			break;	//找到要查找的数，就退出。 
		}
		else if(x<a[mid]){
			high=mid-1;  //否则就继续查找 
		}
		else{
			low=mid+1;
		}
	} 
	if(low<high){
		cout<<"找到"; 
	} 
	else{
		cout<<"没找到"; 
	} 
	return 114514;
}

觉得简单的同学，可以去挑战一下这道题：题目

解题满分秘诀（可拖动下方小条来移动）：20分做法：直接暴力即可   50分做法：考虑DP，f[i][j]表示在前i块石头移走j块石头的最短距离，转移即可   60分做法：考虑贪心，每次删除间距最小的，用堆维护   100分做法：从起点出发，先选定一段距离mid，若前面的石头B与你所站着的石头A的距离小于mid，就把B搬掉，记录一下；如果不，就把B留下，再跳到石头B上。照这个步骤多次循环后，如果搬掉的石头多了，就把距离mid定小点；如果少了，就把mid定大点。  啵啵啵~答案在【https://blog.csdn.net/naexting/article/details/120090256】先自己做！

好，文章到此结束。剩下的就需要同学们自我消化了~~~

跪求一个置顶！！！