一、定义：
折半查找也称二分法查找，是一种在有序数组中查找某一特定元素的搜索算法。这种方法要求待查找的表顺序存储而且必须是有序的。
二、查找过程
首先计算表中间的位置，将表中间位置处的关键字与查找的关键字进行比较，如果相等，则查找成功；否则利用中间位置将表分为前、后两个子表，如果中间位置的关键字大于查找的关键字，则查找前子表，否则查找后子表。重复上面的过程，直到找到要查找的关键字为止，否则查找失败不存在此关键字。
例：对{2,5,6,9,17,23,54}中的17进行查找

如图，初始时先让low和high在数据集合的头和尾，中间位置为mid,low=0,high=6.所以mid=（0+6）/2=3，即3位置处，关键字为9不等于17，因为17>9//中间位置的关键字小于要查找的关键字，所以应该在后半子表中。接着再计算后半子表中的中间位置：此时low=mid+1,high=high,则mid=(4+6)/2=5，即5处的关键字为23,23不等于17,且17<23//中间位置的关键字大于要查找的关键字，所以应该在前半子表中，前半子表的中间位置为：此时low=low,high=mid-1,则mid=(4+4)/2=4,4处的关键字为17，查找成功结束。以此方法，如果查找的关键字在数据集合中不存在，会出现low>high。所以结束条件为low>high或者找到关键字为止.

a[mid]==key   return mid;//中间位置的关键字等于要查找的关键字
a[mid]<key    low = mid + 1;//中间位置的关键字小于要查找的关键字
a[mid]>key   high = mid - 1;//中间位置的关键字大于要查找的关键字

三、实现
方法一：非递归方法

#include<stdio.h>
#define N 7int Search(int a[],int low,int high,int key){int mid;while(low<=high){mid = (low+high)/2;if(a[mid]==key){//查找到return mid;}else if(a[mid]<key){//中间位置的关键字小于要查找的关键字low = mid+1;}else{//中间位置的关键字大于要查找的关键字high = mid-1;}}return -1;
}int main(void)
{int a[N]={2,5,6,9,17,23,54};int i,key;printf("请输入你要查找的值:");scanf("%d",&key);i = Search(a,0,N-1,key);printf("%d",i);return 0;
}

递归方法

#include<stdio.h>
#define N 7int Search(int a[],int low,int high,int key){int mid;if(low>high){return -1;}else{mid = (low+high)/2;if(a[mid]==key){return mid;}else if(a[mid]<key){//中间位置的关键字小于要查找的关键字return Search(a,mid+1,high,key);}else{//中间位置的关键字大于要查找的关键字return Search(a,low,mid-1,key);}}
}int main(void)
{int a[N]={2,5,6,9,17,23,54};int i,key;printf("请输入你要查找的值:");scanf("%d",&key);i = Search(a,0,N-1,key);printf("%d",i);return 0;
}

二分查找会生成一棵二叉查找树
时间复杂度o(lbn)