各位看官们，大家好，上一回中咱们说的是顺序查找的例子，这一回咱们说的例子是：二分查找。闲话休提，言归正转。让我们一起talk C栗子吧！
看官们，我们在上一回中说了查找的相关内容，并且介绍了一种查找方法：顺序查找。大家还记得吗？台下有看官说：记得呢。我刚想表扬一下这位看官，但是话还没有出口，这看官就又说了：就是不知道哪个人最后找到钥匙没有。我什么表扬的话也没有说，大声吆喝道：“这一回中，我给大家介绍一种新的查找方法：二分查找法。或者叫折半查找法也可以。”
在介绍二分查找法之前，我们还遵守上一回中约定的前提条件：查找的范围限定为某些容器，这些容器就是我们前面说过的链表，栈，队列 。查找的内容就是这些容器中的某个元素。二分查找法就是先确定查找内容在容器中的查找区间，然后逐步缩小查找区间，直到区间中为空（也就是区间中没有元素）。在查找过程中比较查找的内容与容器中的元素，如果查找的内容与容器中的某个元素相同，那么表示已经从容器中查找到想要的内容了。我们可以称其为：查找成功。如果查找的内容与容器中的所有元素都不相同，那么表示容器中没有我们想要查找的内容。我们可以称其为：查找失败。
在使用二分查找法之前，我们需要确保容器中的元素是有序的，比如容器中的元素按照从小到大的顺序存放。只有确保容器中的元素有序，才能确定查找区间。接下来我们说说二分查找法的实现步骤。
- 1.首先确定查找区间。第一次查找时把整个容器定义为查找区间。第一次以后查找时查找区间会变化；
- 2.拿出位于容器中间的元素，让它与我们想要查找的内容进行比较。如果二者相等，那么查找成功。这时 可以停止查找了。如果二者不相等，那么进入下一步；
- 3.如果容器中间的元素比我们想要查找的内容大，那么把容器中间到容器结尾这部分区间定为新的查找区 间。然后回到步骤1中，继续进行查找；
- 4.如果容器中间的元素比我们想要查找的内容小，那么把容器开始到容器中间这部分区间定为新的查找区 间。然后回到步骤1中，继续进行查找；
- 5.重复步骤1到步骤4，直到查找的区间变空时停止查找。
- 6.确定停止查找的原因，如果是在步骤2中停止的查找，那么我们可以说查找成功。如果是在步骤5中停止 的查找，那么我们可以说查找失败。
大家可以看到，在查找过程中，没有划分为查找区间中的容器空间，我们不再需要去这些空间中查找，这 样可以节省查找时间。而且整个查找过程中，我们在不断地缩小查找区间，因此节省的时间是相当可以观 的，当容器很大时，更能体现出来。
二分查找法与我们前一回说的顺序查找法相比较而言，效率要高。因此在程序中经常使用该方法去查找需要的内容。当然了，如果查找的容器比较小，使用二分查找法时，还需要给容器中的元素进行排序，这也需要消耗时间的，排序时间再加上二分查找时间估计比顺序查找的时间还有长一些。所以在小容器中查找内容时，使用简单的顺序查找方法就可以了，正所谓杀鸡焉用牛刀。如果查找的窗口比较大，那么最好还是使用二分查找法，不然使用顺序查找那把”小刀“，不知道猴年马月才能杀掉一头”大牛“。
看官们，详细的代码如下所示，请大家参考：
1 /* **************************
2 * Source file of Binary Search
3 * *************************/
4
5 #include<stdio.h>
6
7 #define SUCCESS 0
8 #define FAILE 1
9
10 #define SIZE 10 //容器大小定义为10
11
12 typedef int Elmt; //把int当作容器中元素的类型，实际中可以使用其它的类型或者自己定义一个元素类型
13
14 //二分查找函数,头文件的内容比较简单，因此把头文件和源文件放在一起
15 int BinSearch(Elmt* a,int size,Elmt e)
16 {
17 int i =0;
18 int low,mid,high;
19 int flag = 0;
20
21 if(NULL == a)
22 return FAILE;
23
24 low = 0;
25 high = size;
26 mid = (high + low)/2;
27
28 if(*(a+low)==e)
29 return SUCCESS;
30
31 if(*(a+high-1)==e)
32 return SUCCESS;
33
34 while(low<=high)
35 {
36 if(*(a+mid)>e)
37 {
38 high= mid-1;
39 mid = (high + low)/2;
40 }
41 else if(*(a+mid)<e)
42 {
43 low = mid+1;
44 mid = (high + low)/2;
45 }
46 else
47 {
48 flag = 1;
49 break;
50 }
51 }
52
53 if(1 == flag)
54 {
55 flag = 0;
56 return SUCCESS;
57 }
58 else
59 return FAILE;
60
61 }
62
63 int main()
64 {
65 int i= 0;
66 int f = 0; //想要查找的内容
67 Elmt array[SIZE] = {0}; //简单起见，使用数组做为容器
68
69 while(i++ < SIZE) //初始化容器
70 array[i-1] = i;
71
72 printf("the elmt of array is : ");
73 i=0;
74 while(i < SIZE)
75 printf("%d ",array[i++]);
76 printf(" \n");
77
78 f = 3; //确定想要查找的内容
79 //f = 59; //确定想要查找的内容
80 if(!BinSearch(array,SIZE,f))
81 printf("%d is found in array\n",f);
82 else
83 printf("%d is not found in array\n",f);
84
85 return SUCCESS;
86 }
看官们，其实我们在日常生也使用过二分查找法，只是没有太在意而已。为了大家理解容易，我们举个日 常生活中的例子，该例子还是上一回结尾时的例子：小明回家时需要使用钥匙开门，这时就去衣服口袋里 找，这便是在确定查找区间。小明穿的是T恤，没有口袋，所以他就去裤子的口袋里找，这便缩小查找区 间，同时也指定了新的查找区间；裤子上的口袋都找遍了，还是没有找到钥匙。我的钥匙去哪儿了？这还 用问，肯定是丢了呀。哈哈！
各位看官，关于二分查找的例子咱们就说到这里。欲知后面还有什么例子，且听下回分解。