二分查找查找关键字的范围

无情阅读：899 2020-10-19 15:34:56 评论：0

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

二分查找对有序表查找的时间复杂度为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

输出：

标签:加密算法面试

声明

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，请转载时务必注明文章作者和来源，不尊重原创的行为我们将追究责任；3.作者投稿可能会经我们编辑修改或补充。

二分查找 查找关键字的范围

二分查找查找关键字的范围