二分查找与二分答案（1.）

1.二分查找

大家还知道怎么在一本很厚的词典查找一个单词吗？字典中的单词是按照“字典序”进行排序的，比如 code<pan<pancake 。如果我们要找一个单词，就要将字典从中间翻开，然后将这面单词跟想要找的单词比较。如果这面单词在需要寻找的单词之前，就将字典往后翻，否则就往前翻，直到找到准确的单词为止。

大家可以发现，越接近需要查询的单词，翻动书面的页数就越少。你肯定不会从第一页开始一面一面翻，逐个查看每个单词是否就是自己想要查的单词，这样做就太慢了。虽然实际情况不是那么精确，但是基本上使用了“二分思想”。

如果序列是有序的，就可以通过二分查找快速定位所需要的数据。除此之外，二分思想还能求出可行解的最值问题，比如想知道某款手机最高能多少楼高度摔下来而不会摔坏，使用二分的方式可以用最小实验次数就能得到结果（当然你需要准备好几个样品）。

推荐题单：（洛谷题单）【算法1-6】二分查找与二分答案。

例题1

P2249 【深基13.例1】查找

输入样例：

        11 3

        1 3 3 3 5 7 9 11 13 15 15

        1 3 6

输出样例：

        1 2 -1

分析：

        直接从头到尾搜索一遍查找数字是不可行的。一旦数字太多，便容易RE（超出时间限制），效率太低。不过，这种做法没有用到题目没有用到题目给出的一个条件：保证序列数组为升序（如果数组不是按顺序排列就需要一个排序函数----sort）能否得到时间复杂度更优的做法呢？

        回顾一下“翻字典”的例子，要在整本字典中查找一个单词，安排首尾两个指针：首指针是第一页，尾指针是最后一页。然后将这本字典从中间分为前半本和后半本，并且将分割处的单词和需要找的单词进行比较，要么运气比较好，刚好分割处就是我们要找的单词，要么分割处的单词在我们要查找的单词前----就继续只看前半部分字典，否则只看后半部分字典。改变首尾指针，缩小查找范围，直到找到需要的单词为止。

代码：

#include<iostream>
using namespace std;
int Sert(int a[],int n,int x){
	int high=x-1,low=0,mid;
	while(low<=high){
		mid=(low+high)/2;//中间页数
		if(a[mid]>=n) high=mid-1;//取区间前一半
		else low=mid+1;//取区间后一半
	}
	if(low<x&&a[low]==n) return low+1;//找到了
	return -1;//没找到
}
int a[1000000],m,b,n;
int main(){
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	while(m--){
		scanf("%d",&b);
		printf("%d ",Sert(a,b,n));
	} 
	return 0;
} 

未完待续