折半查找法（迭代实现）,数据结构与算法,技术交流,鱼C论坛

小甲鱼 发表于 2013-2-23 04:22:51

折半查找法（迭代实现）

如果从文件中读取的数据记录的关键字是有序排列的，则可以用一种效率比较高的查找方法来查找文件的记录，这就是折半查找法，又称为二分法搜索。

折半查找的基本思想是：减小查找序列的长度，分而治之地进行关键字的查找。

折半查找的实现过程是：先确定待查找记录的所在范围，然后逐渐缩小这个范围，直到找到该记录或查找失败（查无该记录）为止。

例如有序列：1 1 2 3 5 8 13 21 34 55 89（该序列包含 11 个元素，而且关键字单调递增。），现要求查找关键字 key 为 55 的记录。

我们可以设指针 low 和 high 分别指向关键字序列的上界和下界，指针 mid 指向序列的中间位置，即 mid = (low+high)/2。

No pic you say a J8 之图1：

首先将 mid 所指向的元素与 key 进行比较，因为我们这里 key = 55，大于 8，这就说明待查找的关键字一定位于 mid 和 high 之间。于是我们执行 low = mid+1; mid = (low+high)/2;

No pic you say a J8 之图2：

然后再将 mid 所指的 34 与 key 进行比较，仍然 mid < key，所以继续执行 low = mid+1; mid = (low+high)/2;

No pic you say a J8 之图3：

接下来仍然将 mid 所指的元素与 key 进行比较，结果相等，查找成功，可喜可贺，可口可乐！

返回 mid 的指针值，程序结束！

假设我们要查找的关键字 key = 88，那么上述的查找还要继续进行下去 low = mid+1; mid = (low+high)/2;

No pic you say a J8 之图4：

完整实现代码如下：

// ********************************
// By 小甲鱼，http://www.fishc.com
// ********************************
#include <stdio.h>

int bin_search( int str[], int n, int key )
{
   int low, high, mid;

   low = 0;
   high = n-1;

   while( low <= high )
   {
            mid = (low+high)/2;
            if( str == key )
            {
                     return mid;             // 查找成功
            }
            if( str < key )
            {
                     low = mid + 1;    // 在后半序列中查找
            }
            if( str > key )
            {
                     high = mid - 1;    // 在前半序列中查找
            }
   }

   return -1;                            // 查找失败
}

int main()
{
   int str = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
   int n, addr;

   printf("请输入待查找的关键字: ");
   scanf("%d", &n);

   addr = bin_search(str, 11, n);
   if( -1 != addr )
   {
            printf("查找成功，可喜可贺，可口可乐! 关键字 %d 所在的位置是: %d\n", n, addr);
   }
   else
   {
            printf("查找失败!\n");
   }

   return 0;
}

506076894 发表于 2013-2-23 09:06:15

这个好，强大的算法

缘缘发表于 2013-2-26 19:48:59

写了个递归的：
#include<stdio.h>
#define SIZE 10
typedef int ElemType;
int refind(ElemType *data,int begin,int end,ElemType num);
int main(void){
         ElemType data={10,20,30,40,50,60,70,80,90,100};
         ElemType num;
         for(int i = 0;i<SIZE;i++)
               printf("%d ",data);
         printf("\n请输入要查找的数据:\n");
         scanf("%d",&num);
         int flag = refind(data,0,SIZE,num);
         printf("位置为:%d\n",flag);
         return 0;
}
/
//递归
int refind(ElemType *data,int begin,int end,ElemType num)
{
         if(begin > end)
         {
                  printf("没找到\n");
                  return -1;
         }

         int mid = (begin+end)/2;

         if(data == num)
         {
                  return mid;
         }else if(data <= num)
                  return refind(data,mid+1,end,num);
         else
                  return refind(data,begin,mid-1,num);
}

YYB 发表于 2013-2-27 12:56:43

我有个问题，如果mid的值不是整数怎么弄啊？比如LOW = 0 High = 9，MID =4.5 这个时候怎么办啊？str不可以啊

小甲鱼 发表于 2013-2-27 14:53:56

YYB 发表于 2013-2-27 12:56 static/image/common/back.gif
我有个问题，如果mid的值不是整数怎么弄啊？比如LOW = 0 High = 9，MID =4.5 这个时候怎么办啊？str不 ...

这里的MID是向下取整└MID┘

feitianqu 发表于 2013-3-14 22:25:22

（）冒充下高手（）'“/"是求整不是除法哦

zhengfeilong 发表于 2013-8-11 20:38:12

不错学习下。

轻云流风 发表于 2013-9-18 16:21:45

顶起，不错呀

330740120 发表于 2013-9-28 09:31:27

谢谢小甲鱼！存钱买视频！

铖子发表于 2013-10-8 11:31:59

强烈支持楼主ing……楼下的听好了……

bare 发表于 2013-10-9 05:43:04

数组元素再加一个就挂了？？:curse:

许许发表于 2014-4-7 15:01:07

int binsearch_recursion(int a[], int low, int high, int key)
{
if(low > high)
{
return -1;
}
int mid = (low + high)/2;
if(a > key)
{
return binsearch_recursion(a, low, mid-1, key);
}
else if(a < key)
{
return binsearch_recursion(a, mid+1, high, key);
}
else
{
return mid;
}

}

沉默默 发表于 2014-7-25 20:37:40

# include <stdio.h>

int bin_search(int *, int, int);

int main(void)
{
int a = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};

printf("%d\n", bin_search(a, 11, 21));

return 0;
}

int bin_search(int * a, int n, int val)
{
int pos, low, hig, mid;

for (low=0, hig=n-1, mid=(low+hig) / 2; low <= hig; mid=(low+hig) / 2) {
if ( val == a )
return mid + 1;
else if ( a > val )
hig = mid - 1;
else
low = mid + 1;
}

return -1;
}

wxbmelisky 发表于 2015-1-3 17:02:19

这个学习对我帮助很大啊好好学习

雪是梅之香 发表于 2015-1-19 10:29:02

现在才学习，附上我的代码：
#include <stdio.h>
#include <stdlib.h>

int find(int num[],int low,int high,int a)
{
int mid=(low+high)/2;
if(low<=high)
{
   if(num==a)
   {
         return mid;
   }
   if(num>a)
   {
         return find(num,low,mid-1,a);
   }
   if(num<a)
   {
         return find(num,mid+1,high,a);
   }
}else
{
   return -1;
}
}
void main()
{
int num[]={1,1,2,3,5,8,13,21,34,55,89};
int n,result;
printf("请输入你要查找的数：");
scanf("%d",&n);
result=find(num,0,10,n);
if(result==-1)
{
   printf("不存在此数");
}else
{
   printf("你要找的数在第%d个位置。",result+1);
}
}

天外飞mao 发表于 2015-3-15 11:29:07

感谢小甲鱼

CutePrince 发表于 2015-3-17 22:26:14

RE: 折半查找法（迭代实现）

强烈支持楼主ing……
用迭代实现了一下：
#include <stdio.h>
#include <stdlib.h>

int bin_serach(int str[], int n, int key)
{
int low, mid, high;

low = 0;
high = n - 1;

while(low <= high)
{
   mid = (low + high)/2;
   if (str == key)
   {
         return mid;
   }
   else if (str < key)
   {
         low = mid + 1;
   }
   else {
         high = mid - 1;
   }
}
return -1;
}

int getAddr(int str[], int key, int low, int high)
{
if (low > high)
   return -1;

int mid = (low + high) / 2;

if (key == str)
   return mid;

if (str < key)
{
   low = mid + 1;
}
else if (str > key)
{
   high = mid - 1;
}

return getAddr(str, key, low, high);
}

int main()
{
int str = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
int n, addr;

printf("请输入要查询的数字：");
scanf("%d", &n);

//addr = bin_serach(str, 11, n);
addr = getAddr(str, n, 0, 11);

if (-1 != addr)
{
   printf("查找成功，查询数字%d所在的位置是：%d\n", n, addr);
}
else
{
   printf("查找失败");
}

return 0;
}

8938 发表于 2015-5-14 21:19:19

{:1_1:}

MozzieChow 发表于 2015-9-14 21:51:51

//做作业

#include<stdio.h>

int bin_search(int arr[], int low, int high, int key);

void main()
{
int arr={10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int key;
printf("\n请输入要查找的数据:\n");
scanf("%d", &key);
int addr = bin_search(arr, 0, 9, key);
if(addr != -1)
{
printf("key: %d, address: %d\n", key, addr);
}
else
{
printf("输入错误");
}
}

int bin_search(int arr[], int low, int high, int key)
{
int mid = (low + high)/2;
if(key == arr)
{
return mid;
}

if(key <= arr)
{
high = mid - 1;
bin_search(arr, low, high, key);
}

if(key >= arr)
{
low = mid + 1;
bin_search(arr, low, high, key);
}

else
{
return -1;
}
}

love_programe 发表于 2015-10-11 14:22:11

这个算法貌似就是那个所谓的“二分法”吧！！

页: [1] 2

鱼C论坛's Archiver

折半查找法（迭代实现）

RE: 折半查找法（迭代实现）