二分查找法
1.什么是二分查找法
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。（From Baidu Baike)
2.二分查找的算法要求
①.数据必须有序排列；
②数据必须顺序存储。
3.二分查找的时间复杂度
O()=O(logn)
4.二分查找的实现原理
被查找的数据要先按顺序（这里是从小到大）存储在数组a里，并且知道要查找的数据key。
首先我们定义四个变量，分别为left,right,mid,ret。其中left、right和mid作为指向数组下标的变量，ret储存查找的结果（下标）并返回其值。
查找开始，首先让left和right指向数组的两端，并让ret为-1（返回-1表示没有查找到），求出left和right的中间值mid，比较数组a[mid]与被查找元素key的关系。
①若a[mid] = key，则表示找到被查找元素，查找结束；
②若a[mid] > key，则表示key应该比a[mid] 小，所以让right = mid -1，并继续查找；
③若a[mid] < key，则表示key应该比a[mid] 大，所以让left = mid + 1，并继续查找；
图
由此可见，整个查找的过程一直在继续，直到找到数据或者查找完数据，那么查找完数据的条件是什么呢？这里直接给出答案，有兴趣的读者可以写一段代码调试查看或者在纸上演算一下。
right > ltft
由上述条件可以得知，查找要放在一个循环里，或者用递归实现。下面给出代码。
5.二分查找的代码
/* Title: 二分查找（循环实现） Author：Pengwill Date:2016-08-29 Blog:http://blog.csdn.net/pengwill97 */
#include<stdio.h>
int main()
{
int a[] ={1,5,6,8,9,10,15,16,17,51,56};//这里首先定义了一个有序的数组，如果无序，先排序
int left,right,mid,ret,k;
ret = -1;//初始化，-1表示没有查找到数据
left = 0;
right = sizeof(a)/sizeof(a[0]);
scanf("%d",&k);//输入要查找的数据
while(right>left){//注意循环的条件
mid = (right+left)/2;
if(a[mid]==k){
ret = mid;
break;
}else if(a[mid] > k){
right = mid-1;
}else{
left = mid+1;
}
}
printf("%d",ret);
return 0;
}