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