二分查找

二分查找：查找已排序数组中的某个值

算法过程：

将欲查找元素与数组中间值（a[mid]）对比，每次查找的数组大小减半。如果欲查找的值存在于数组中，则必定在某次循环中通过a[mid]返回

 1 #include <stdio.h>
 2 
 3 int main(void){
 4 　　int i = 0, mid, key, len;
 5 　　puts("enter the length of string:");
 6 　　scanf("%d", &len);//这里之后原来有一句getchar();为了执行错误1的语句，消除scanf后留下的换行符 
 7 
 8 　　int a[len];
 9 　　int lo = 0, hi = len - 1;
10 　　mid = (lo + hi)/2;
11 　　puts("enter a string of sorted number:");
12 　　while(i<len) //错误1：这里原来是用while((a[i] = getchar())!='
')i++;注意a是一个整形数组！getchar检索的是字符型！ 
13 　　　　scanf("%d", &a[i++]);
14 
15 　　puts("enter a key:");
16 　　scanf("%d", &key);
17 　　while(lo<=hi){
18 　　　　if(key<a[mid]){
19 　　　　hi = mid - 1;
20 　　　　mid =(lo + hi)/2;    
21 　　　　}
22 　　　　else if(key>a[mid]){
23 　　　　　　lo = mid + 1;
24 　　　　　　mid = (lo + hi)/2;    
25 　　　　}
26 　　　　else{
27 　　　　　　printf("the key %d in string a is a[%d]
", key, mid);
28 　　　　　　break;
29 　　　　}    
30 　　} 
31 　　if(lo>hi)
32 　　puts("key is not found.
");
33 　　return 0;
35 }

查找的次数最多可能为：log2(N)次（N为数组大小），因为查找次数最多时最后一次查找为2个数中的一个，每次查找都排除掉一半的数，2^x = N，x为查找次数