您当前的位置:首页 > 计算机 > 编程开发 > C语言

C语言二分法查找算法(附带源码)

时间:10-08来源:作者:点击数:

顺序查找是从第一个数据开始比较,直到找到目标数据。当数据量较大时,顺序查找的效率就会降低。

将数据进行排序以后,我们就可以使用另一种更加有效的查找方法:二分法查找。二分法查找的思想是,对于已经按照从小到大的顺序排列好的 N 个数据,取出排在中间位置的数据进行比较,如果等于要找的数则查找结束;如果比要找的数大,则要找的数据一定在左边部分,则在左边数据中继续用类似的方法查找;如果比要找的数小,则在右边数据中继续用类似的方法查找。在整个过程中,查找的数据范围每次都被分成两半,因而称为二分法查找

例如,在有序数据 {26,30,45,55,60,61,62,65,70,78,99} 中查找 55 的过程如图 1 所示。

二分法查找
图 1:二分法查找

上一节《C语言顺序查找算法》中的问题用二分法实现查找的代码如下:

C语言代码清单 1:根据输入的个人成绩获得考试排名(二分法查找)

#include <stdio.h>
#include <stdlib.h>
int main( )
{
    int i,S;
    int a[100];
    printf("从低到高输入成绩(空格分隔),\n");   
    printf("全部输入后,输入0并回车!\n");
    for(i=0;i<100;i++){        //用for循环给数组元素赋值
        scanf("%d",&a[i]);
        if(a[i]==0) break;     //接收到0,则退出循环
    }
    printf("名次查询(输入0结束查询):\n");
    int L,R,mid,R0=i;
    do{
        printf("输入成绩:");
        scanf("%d",&S);
        if(S==0) break;        //输入0结束查询
        L=1;R=R0;
        while(L<=R){
            mid=(L+R)/2; 
            printf("%d %d %d\n",L,mid,R);
            if(a[mid-1]==S) break;           //找到目标退出循环
            if(a[mid-1]>S) R=mid-1;          //进入左半区间
            else if(a[mid-1]<S) L=mid+1;     //进入右半区间
                printf("%d A %d\n\n",L,R);
        }
        if(a[mid-1]==S)
            printf("%d\n",mid); //输出名次
        else
            printf("未找到该成绩!");
    }while(S!=0);
    system("pause");
    return 0;
}

运行结果:

从低到高输入成绩(空格分隔),
全部输入后,输入0并回车!
51 60 65 77 83 85 87 99 0
名次查询(输入0结束查询):
输入成绩:60
1 4 8
1 A 3

1 2 3
2

上述代码中,录入的成绩从大到小排序,用 L 指示最左端数据,R 指示最右端数据,mid 指示中间位置的数据。查找值与 mid 处的数据相比较,如果 mid 处的数小,则查找值在其左侧,改变 R 的值;如果 mid 处的数大,则查找值在其右侧,改变 L 的值;继续在 L 和 R 之间的数据中用同样的方法查找,直到找到要找的数或 L 和 R 位置重合。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门