折半查找法（迭代实现）

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

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

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

例如有序列：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[mid] == key )
                {
                        return mid;                // 查找成功
                }
                if( str[mid] < key )
                {
                        low = mid + 1;        // 在后半序列中查找
                }
                if( str[mid] > key )
                {
                        high = mid - 1;        // 在前半序列中查找
                }
        }

        return -1;                                // 查找失败
}

int main()
{
        int str[11] = {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[SIZE]={10,20,30,40,50,60,70,80,90,100};
            ElemType num;
            for(int i = 0;i<SIZE;i++)
                    printf("%d ",data[i]);
            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[mid] == num)
            {
                      return mid;
             }else if(data[mid] <= 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[4.5]不可以啊

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

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

登录/注册后可看大图

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

这里的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[mid] > key)
{
return binsearch_recursion(a, low, mid-1, key);
}
else if(a[mid] < 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[11] = {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[mid] )
return mid + 1;
else if ( a[mid] > 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[mid]==a)
        {
            return mid;
        }
        if(num[mid]>a)
        {
            return find(num,low,mid-1,a);
        }
        if(num[mid]<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

强烈支持楼主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[mid] == key)
        {
            return mid;
        }
        else if (str[mid] < 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[mid])
        return mid;

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

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

int main()
{
    int str[11] = {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]={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[mid])
        {
                return mid;
        }
        
        if(key <= arr[mid])
        {
                high = mid - 1;
                bin_search(arr, low, high, key);        
        }
        
        if(key >= arr[mid])
        {
                low = mid + 1;
                bin_search(arr, low, high, key);        
        }

        else
        {
                return -1;
        }
}

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

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

账号		自动登录	找回密码
密码			立即注册

[技术交流] 折半查找法（迭代实现）

马上注册，结交更多好友，享用更多功能^_^

评分

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