二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。

二分查找对有序表查找的时间复杂度为lg(n)。

一般的二分查找只是查找给定元素在数组中的位置或者是有存在给定的元素。

下面的程序实现的功能是:

  在顺序保存、有序的数组中查找给定关键字K的范围

程序:

 1 #include <stdio.h> 
 2 int values[]={1,2,3,5,7,7,7,7,9,10,10,10,12}; 
 3  
 4 /* 
 5 @low:查找范围的起始坐标 
 6 @high:查找范围的结束坐标 
 7 @key:待查找的关键字 
 8 @tag:查找标记。tag=0,表示查找关键字的最小坐标;tag=1,表示查找最大坐标 
 9 */ 
10 int getRange(int low,int high,int key,int tag) 
11 { 
12     int mid; 
13     while(low<=high) 
14     { 
15         mid=(low+high)>>1; 
16         if(values[mid]==key) 
17         { 
18             if(tag==0) 
19             { 
20                 if(mid>low && values[mid-1]==key) 
21                     high=mid-1; 
22                 else 
23                     return mid; 
24             } 
25             else 
26             { 
27                 if(mid<high && values[mid+1]==key) 
28                     low=mid+1; 
29                 else 
30                     return mid; 
31             }            
32         } 
33         else if(values[mid]>key) 
34             high=mid-1; 
35         else 
36             low=mid+1; 
37     } 
38     return 0; 
39 } 
40  
41 int main () 
42 { 
43     int num,key; 
44     int low,high=-1; 
45     num=sizeof(values)/sizeof(int);    //计算数组中的元素个数 
46     printf("The number need to find :"); 
47     scanf("%d",&key); 
48  
49     low=getRange(0,num-1,key,0);    //查找关键字的最小坐标 
50     if(values[low]==key)    //校验是否存在 
51         high=getRange(low,num-1,key,1);    //查找关键字的最大坐标 
52  
53     if(high==-1) 
54         printf("Not exist!!!\n"); 
55     else 
56         printf("Range :[%d~%d]\n",low,high); 
57     return 0; 
58 }
View Code

输出:

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

Horspool 字符串匹配算法讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。