查看: 1138|回复: 0
打印 上一主题 下一主题

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

[复制链接]
跳转到指定楼层
沙发
发表于 2016-6-14 19:05:09 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
今天没事儿,写了一个二分算法应用的例子,用于查找数据在表格(数组)中某个区间的索引值,已在CB中测试通过。
  • /**************************************************
  • ** 文件说明: 二分法查找目标数据所在数组中的位置索引 演示
  • ** 作者    : foxpro2005
  • ** 日期    : 2013-03-12
  • ** QQ      : 5894398
  • **************************************************/
  • #include <stdio.h>
  • int Table[15]={
  •     3,9,16,20,26,31,38,42,47,51,58,66,73,87,98
  • };
  • /**************************************************
  • ** 函数功能: 二分法查找目标数据所在数组中的位置索引
  • **************************************************/
  • int SearchTable(int *pTable, int TabSize, int x)
  • {
  •         int mid, btm = 0, top = --TabSize;
  •         if(x < pTable[btm + 1]){                            // 超出下限,锁定在btm索引值范围
  •                 return btm;
  •         }else if(x < pTable[top]){              // 在表格范围内
  •                 while((top - btm) != 1)                        // 2分法查找区间
  •                 {
  •                         mid = (btm + top) >> 1;         // /2
  •                         if(x > pTable[mid]){
  •                                 btm = mid;
  •                         }
  •                         else if(x < pTable[mid]){
  •                                 top = mid;
  •                         }
  •                         else{
  •                                 return mid;                 // 正好等于mid位所在值
  •                         }
  •                 }
  •                 return btm;                                                // 找到一个区间,并返回这个区间的开始索引值(以向下原则)
  •         }
  •         else{                                                // 超出上限,锁定在top索引值范围
  •                 return top;
  •         }
  • }
  • int main(void)
  • {
  •         int i,x;
  •         for(i=0; i < (sizeof(Table) / sizeof(Table[0])); i++){
  •                 if(i==0)
  •                         printf("Table={%d",Table);
  •                 else
  •                         printf(",%d",Table);
  •         }
  •         printf("}\n");
  •         printf("Enter -1 can be end\n");
  •         while(1){
  •                 printf("Please intput a new number: ");
  •                 scanf("%d",&x);
  •                 if(x == -1)
  •                         break;
  •                 else{
  •                         printf("\n%d's index is %d\n",x,SearchTable(Table, (sizeof(Table) / sizeof(Table[0])), x));
  •                 }
  •         }
  •         return -1;
  • }



回复

使用道具 举报

您需要登录后才可以回帖 登录 | 加入中科因仑

本版积分规则

快速回复 返回顶部 返回列表