1. 引出问题

二分法有很多很多模板，不同的模板都能解决问题。如果是写程序，只要会其中任意的一种都能拿到满分。

但是，面对填空题的时候，这个问题就有点复杂，因为你即便会了其中一种方法，如果拿出来考你的是一种你没学过的代码模板，那么你还是拿不到分。因此，我们有必要再介绍一些常见的考试模板。

2. 知识回顾和本课学习重点

二分查找分成了 3 大类：

1. 等于查找，一般来说，数组里面的数字不重复（相当于这是一个数学上的集合），我们只需要知道某个值在这个数组里是否存在就可以了。

2. 左边界查找：数组里符合条件的数有可能有多个，我们要找到满足条件的第一个（最小的那个）

3. 右边界查找：数组里符合条件的数有可能有多个，我们要找到满足条件的最后一个（最大的那个）

我们还是针对这 3 种情况来分析，这个改进版的二分查找算法如何实现（分 3 个课件讲解）。

题目描述

请在一个有序递增数组中（不存在相同元素），采用二分查找，找出值 x的位置，如果 x 在数组中不存在，请输出 -1 。

输入格式

第一行，一个整数 n，代表数组元素个数 ( n <= ${10}^6$ )

第二行，n 个数，代表数组的 n 个递增元素 ( 1 <= 数组元素值 <= ${10}^8$ )

第三行，一个整数 x ，代表要查找的数（ 0 <= x <= ${10}^8$）

输出格式

x 在数组中的位置，或者 -1 。

样例

10
1 3 5 7 9 11 13 15 17 19
3

2

我们已经学过了二分查找的算法，在之前的教学中，我们提供了一种比较容易理解的代码

旧方法

#include<bits/stdc++.h>
using namespace std;
int a[1000001],n,x;
int main()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&x);


    if(a[1]>x || a[n]<x ) //如果 x 比区域内最大的数大，或者比区域内最小的数小，那不可能找得到
    {
    	printf("-1");
    	return 0;
	}
	else
	{
		int mid,low,high;
		low = 1;
		high = n;

		while(low+1<high ) // [low,high]起码包含一个数字
		{
	
			mid = (low+high)/2;
			if(a[mid]==x) //找到
			{
				printf("%d",mid);
				return 0;
			}
			else if(a[mid]<x) //中间位置的数比 x 小，意味着 x 只可能在后半区
				low = mid+1;
			else
				high = mid-1; //中间位置的数比 x 大，意味着 x 只可能在前半区
		}
	}	

	return 0;
}

3. 一步到位的二分法模板

所谓一步到位，就是说只有当 low 和 high 重叠了，就剩下 1 个数字了，才退出二分的循环迭代。在这个问题上，有不同的处理方法，现在说的这个方法并非唯一的。模板之间的差别是细微的，但是这个细微的差别又是非常重要的，所以初学者不应该一下子接触多种模板，学一个模板就运用熟练，至关重要。现在我们学的这个模板，是相对比较复杂的，也是比较巧妙的，计算机笔试一般只考这种模板。

对于等于查找来说，代码有几个关键要点：

1. while 循环的运行条件是 low<high

2. 如果 a[mid]==x，马上就可以退出查找了

3. 如果 a[mid]<x，说明 x 在后半区，也就是说如果存在，必定存在于 [mid+1, high] 的范围内

4. 如果 a[mid]>x，说明 x 在前半区，也就是说如果存在，必定存在于 [low,mid-1] 的范围内

5. while 语句每一次循环，[low,high] 都得到是收缩，即便在 low+1==high 的情况下也是继续收缩的。这一点特别关键，只有实现了这一点，while 循环才能结束。

6. 退出 while 循环的时候，大多数情况下是 low==high，还要检验一下。

7. 退出 while 循环的时候有可能 high 有可能跑到 low 前面，所以一般来说数组从下标 1 开始用，否则有可能越界。请见下面的例子：

low=5 和 high=6，也就是说，现在整个搜索区间就剩下两个数组元素 a[5], a[6] 了。假设 a[5]=6, a[6]=8， 然后要找的数 x=3 。所以 mid = （5+6）/2 = 5，我们拿着 a[5] (a[mid]) 和 3 比较。因为 a[5] > 3 ，因此修改了 high ，让 high = mid-1 = 4 。所以，下一次循环的时候 ，low = 5， high = 4 ，high 反而比 low 小了（我们常规的思维，就是 low <= high 的）。当出现 low > high 的时候，其实也说明了在数组内找不到 x 。

完善程序

#include<bits/stdc++.h>
using namespace std;
int a[1000001],n,x;
int search(int x)
{	
	if(x[1]>x||x[n]<x)
		return -1;

	int mid,low=填空(1),high=填空(2);

	while( 填空(3) ) // low 如果 小于 high 就继续循环
	{

		mid = 填空(4); // 这个地方可以有两种填法
		if(a[mid]==x) //找到
			return mid;
		else if(a[mid]<x) //中间位置的数比 x 小，意味着 x 只可能在后半区
			填空(5);
		else //中间位置的数比 x 大，意味着 x 只可能在前半区
			填空(6);
	}
	
	if(a[low]==x)
		return low;
	else
		return -1;
}
int main()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&x);

	printf("%d",search(x));

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}