[分享+交流] 发一个二分算法查找数据所在区间索引值的例子

foxpro2005

今天没事儿，写了一个二分算法应用的例子，用于查找数据在表格（数组）中某个区间的索引值，已在CB中测试通过。

1. /**************************************************
   
2. ** 文件说明: 二分法查找目标数据所在数组中的位置索引 演示
   
3. ** 作者    : foxpro2005
   
4. ** 日期    : 2013-03-12
   
5. ** QQ      : 5894398
   
6. **************************************************/
   
7. #include <stdio.h>
   
8. 
   
9. int Table[15]={
   
10.     3,9,16,20,26,31,38,42,47,51,58,66,73,87,98
    
11. };
    
12. 
    
13. /**************************************************
    
14. ** 函数功能: 二分法查找目标数据所在数组中的位置索引
    
15. **************************************************/
    
16. int SearchTable(int *pTable, int TabSize, int x)
    
17. {
    
18.         int mid, btm = 0, top = --TabSize;
    
19. 
    
20.         if(x < pTable[btm + 1]){                            // 超出下限,锁定在btm索引值范围
    
21.                 return btm;
    
22.         }else if(x < pTable[top]){              // 在表格范围内
    
23.                 while((top - btm) != 1)                        // 2分法查找区间
    
24.                 {
    
25.                         mid = (btm + top) >> 1;         // /2
    
26.                         if(x > pTable[mid]){
    
27.                                 btm = mid;
    
28.                         }
    
29.                         else if(x < pTable[mid]){
    
30.                                 top = mid;
    
31.                         }
    
32.                         else{
    
33.                                 return mid;                 // 正好等于mid位所在值
    
34.                         }
    
35.                 }
    
36.                 return btm;                                                // 找到一个区间,并返回这个区间的开始索引值(以向下原则)
    
37.         }
    
38.         else{                                                // 超出上限,锁定在top索引值范围
    
39.                 return top;
    
40.         }
    
41. 
    
42. }
    
43. 
    
44. int main(void)
    
45. {
    
46.         int i,x;
    
47. 
    
48.         for(i=0; i < (sizeof(Table) / sizeof(Table[0])); i++){
    
49.                 if(i==0)
    
50.                         printf("Table={%d",Table[i]);
    
51.                 else
    
52.                         printf(",%d",Table[i]);
    
53.         }
    
54.         printf("}\n");
    
55.         printf("Enter -1 can be end\n");
    
56. 
    
57.         while(1){
    
58.                 printf("Please intput a new number: ");
    
59.                 scanf("%d",&x);
    
60.                 if(x == -1)
    
61.                         break;
    
62.                 else{
    
63.                         printf("\n%d's index is %d\n",x,SearchTable(Table, (sizeof(Table) / sizeof(Table[0])), x));
    
64.                 }
    
65.         }
    
66. 
    
67.         return -1;
    
68. }
    

复制代码