lzh电子论坛

欢迎来到lzh电子论坛:
如果您对电子技术感兴趣就加入我们吧!在这里互相交流互相学习!主要讨论的方向有:单片机,ARM,PCB板设计,FPGA,汇编,C/C++等方面。
-----lzh电子论坛
lzhbbs.top-me.com
lzh电子论坛

电子的道路是孤独的,要懂得左手温暖右手,要懂得把debug当作快乐去欣赏,去享受,那样你才会成功...

欢迎访问lzh电子论坛。可通过【谷歌,SOSO,搜狗】搜索“lzh电子论坛”直接进入论坛。点击了解论坛详细制度


    折半算法

    分享
    avatar
    黑白子
    论坛版主
    论坛版主

    帖子数 : 10
    威望 : 0
    注册日期 : 13-09-20

    折半算法

    帖子 由 黑白子 于 2013-11-24, 10:29 pm

    最近在工作中发现一个查找的算法,蛮好用的。在此与大家分享一下。
    如何将一个数值,准确快速的在一个递增数组中找到位置。
    例如:
    int array[]={0,2,4,6,8,10,12,14,16,18,20,22,24,26,};
    现在有数a=15;如何快速找到a这个变量在数组中的第几个元素中。
    这种我姑且叫做折半查找。

    先上代码,代码如下:
    int BinarySearch(int *str,int MaxNum,int number)
    {
        int index ,Addr;
        index= MaxNum/4;
        Addr=MaxNum/2-1;
      
        do
        {
            if((number>=str[Addr])&&(number<str[Addr+1])) 
           {
                 break;
           }
           else
           if(number<str[StartAdd])
           {
               Addr += index;
           }
          else
          if(number>=str[StartAdd])
          {
              Addr -= index;
          }
           index = index/2;
        }while(index>0)

        return Addr; 

    }
    函数形参说明:
    1.*str:目标数组
    2.MaxNum:目标数组的长度
    3.number :被查找的数值

    使用这个函数有这样几点需要注明:
    1.数组的长度必须是2的倍率关系,即一定是2的N次方。如果不够,则高位补上比高位大一点的数。如上面数组变为int array[]={0,2,4,6,8,10,12,14,16,18,20,22,24,26,27,27};补上两个27(比26大就行),总计十六个数。
    2.数组元素必定是递增的。
    3.形参MaxNum为2的倍率。

    上面调用函数为  addr=BinarySearch(array,16,a);




    有什么问题请提出来,由于工作电脑在办公室的,仓促打字难免有些许错误。请高手指点。
    avatar
    Admin
    管理员
    管理员

    帖子数 : 869
    威望 : 15
    注册日期 : 12-11-23
    年龄 : 25

    回复: 折半算法

    帖子 由 Admin 于 2013-11-24, 11:46 pm

    哦哦,,在大多情况下比一个个查找快多了Embarassed
    avatar
    黑白子
    论坛版主
    论坛版主

    帖子数 : 10
    威望 : 0
    注册日期 : 13-09-20

    回复: 折半算法

    帖子 由 黑白子 于 2013-11-28, 11:23 pm

    补充
    关于折半查找,其实还有一个更为简洁的算法,这个算法不需要限制一定是2的倍率个数,使用范围更为广泛,也更为让人容易理解,闲话少说,直接代码,
    int BinarySearch(int *str,int endaddr,int startaddr,int number)
    {
        int Addr;
      
        do
        {
            Addr   (endaddr +  start addr)/2;
           if((number>=str[Addr])&&(number<str[Addr+1])) 
           {
                 break;
           }
           else
           if(number<str[StartAdd])
           {
                  endaddr     Addr  ;
           }
          else
          if(number>=str[StartAdd+1])
          {
               startaddr      Addr  ; 
          }
       
        }while( endaddr >start addr )

        return Addr; 

    } 



    大致就是这个样子的,些许细节问题,自己查看,有问题欢迎留言,
    avatar
    Admin
    管理员
    管理员

    帖子数 : 869
    威望 : 15
    注册日期 : 12-11-23
    年龄 : 25

    回复: 折半算法

    帖子 由 Admin 于 2013-11-29, 5:59 pm

    呵呵,刚哥给程序来点注释撒
    avatar
    holwold
    中级会员
    中级会员

    帖子数 : 39
    威望 : 0
    注册日期 : 13-05-06

    回复: 折半算法

    帖子 由 holwold 于 2013-11-30, 1:17 am

    楼主,这个算法在哪方面用的多啊

      目前的日期/时间是2018-04-25, 6:54 am