请选择 进入手机版 | 继续访问电脑版
    查看: 652|回复: 0

    C语言二分查找(折半查找)算法及代码

    [复制链接]

    2

    主题

    2

    帖子

    6

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    6
    基情
    4
    发表于 2016-9-11 23:24:23 | 显示全部楼层 |阅读模式
    二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列。该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分。接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解。
    #include <stdio.h>
    
    binarySearch(int a[], int n, int key){
        int low = 0;
        int high = n - 1;
        while(low<= high){
            int mid = (low + high)/2;
            int midVal = a[mid];
            if(midVal<key)
                low = mid + 1;
            else if(midVal>key)
                high = mid - 1;
            else
                return mid;
        }
        return -1;
    }
    
    int main(){
        int i, val, ret;
        int a[8]={-32, 12, 16, 24, 36, 45, 59, 98};
        for(i=0; i<8; i++)
            printf("%d\t", a);
    
        printf("\n请输人所要查找的元素:");
        scanf("%d",&val);
    
        ret = binarySearch(a,8,val);
    
        if(-1 == ret)
            printf("查找失败 \n");
        else
            printf ("查找成功 \n");
    
        return 0;
    }
    运行结果:
    
    -32    12    16    24    36    45    59    98
    请输入所要查找的元素:12
    查找成功
    在上面的代码中,我们成功地通过二分査找算法实现了查找功能,其实现过程如下图所示。

    C语言二分查找(折半查找)算法及代码

    C语言二分查找(折半查找)算法及代码

    二分査找算法的査找过程

    在如上图所示的查找过程中,先将序列中间位置的元素与所要査找的元素进行比较,发现要査找的元素位干该位置的左部分序列中。接下来将mid的左边一个元素作为 high,继续进行二分査找,这时mid所对应的中间元素刚好是所要査找的元素,査找结束,返回査找元素所对应的下标。在main函数中通过返回值来判断査找是否成功,如果査找成功.就打印输出“査找成功”的信息,否则输出“査找失畋”的信息。
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|小黑屋|网站地图|DZ商业模板|VR福利资源|嵌入式Linux论坛 ( 粤ICP备15085165号-2

    GMT+8, 2017-8-23 18:08 , Processed in 0.249600 second(s), 10 queries , File On.

    Powered by 深嵌论坛 X3.3

    © 2001-2013 Comsenz Inc.

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