数组07 – 零基础入门学习C语言29

第六章:数组07

让编程改变世界

Change the world by program

二维数组程序举例 — 二分法举例

假设在数组a中的数据是按由小到大顺序排列的:

-12 0 6 16 23 56 80 100 110 115,从键盘上输入一个数,判定该数是否在数组中,若在,输出所在序号。

TIPS:

第一步:设low、mid和high三个变量,分别指示数列中的起始元素、中间元素与最后一个元素位置, 其初始值为low=0,high=9,mid=4,判断mid指示的数是否为所求,mid指示的数是23,不是要找的80,须继续进行查找。

宽客网,量化投资,宽客俱乐部

二分法原理

第二步:确定新的查找区间。因为80大于23,所以查找范围可以缩小为23后面的数,新的查找区间为[56 80 100 110 115 ],low,mid,high分别指向新区间的开始、中间与最后一个数。实际上high不变,将low(low=mid+1)指向56,mid (mid=(low+high)/2)指向100,还不是要找的80,仍须继续查找。

宽客网,量化投资,宽客俱乐部

二分法原理

第三步:上一步中,所找数80比mid指示的100小,可知新的查找区间为[56 80],low不变,mid与high的值作相应修改。mid指示的数为56,还要继续查找。

宽客网,量化投资,宽客俱乐部

二分法原理

第四步:根据上一步的结果,80大于mid指示的数56,可确定新的查找区间为[80],此时,low与high都指向80,mid亦指向80,即找到了80,到此为止,查找过程完成。

宽客网,量化投资,宽客俱乐部

二分法原理

注意:若在查找过程中,出现low > high的情况,则说明,序列中没有该数,亦结束查找过程。

代码清单:

define M 10

include

void main()

{

        static int a[M] = {-12,0,6,16,23,56,80,100,110,115};

        int n, low, mid, high, found;

        low=0;   

        high=M-1;   

        found=0;

        printf("Input a number to be searched:");

        scanf("%d", &n);

    //以上进行一系列预处理……

    while(low  a[mid])

            low=mid+1;

        else  

            high=mid-1;

    }

    if(found == 1)

        printf("The index of %d is %d",n,mid);

    else

        printf("There is not  %d",n);

}

视频下载
技术, IT技术, 视频教程, C语言

风险提示及免责条款

市场有风险,投资需谨慎。本文不构成个人投资建议,也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资,责任自负。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场,不承担相关法律责任。如若转载,请注明出处。 如若内容造成侵权/违法违规/事实不符,请点击下方“内容举报”进行投诉反馈!
立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部