<kbd id='woaibaidu'></kbd><address id='woaibaidu'><style id='woaibaidu'></style></address><button id='woaibaidu'></button>

          当前位置:主页 > 网络编程 > PHP编程 >
            PHP有序表查找之二分查找(折半查找)算法示例
            2018-02-12 22:02 发布 次浏览

          本文实例讲述了PHP有序表查找之2分查找(折半查找)算法。分享给各人供各人参考,详细以下:

          简介:

          2分查找技术,又称为折半查找。它的条件是线性表中的记载必需是要害码有序(通常从小抵达有序),线性表必需采取顺序存储。

          根本思想:

          在有序表中,取两头记载作为比拟工具,若给定值与两头记载的要害字相等,则查找乐成;若给定值小于两头记载的要害字,则在两头记载的左半区持续查找;若给定值大于两头记载的要害字,则在两头记载的右半区持续查找。不时反复上述进程,直到查找乐成,或一切查找区域无记载,查找失败为止。

          代码:

          <?php
          //2分搜索(折半查找)算法(条件是数组必需是有序数组) 工夫庞大度是 O(logn)
          $i = 0; //存储比照的次数
          //@param 待查找数组
          //@param 待搜索的数字
          function binsearch($arr,$num){
           $count = count($arr);
           $lower = 0;
           $high = $count - 1;
           global $i;
           while($lower <= $high){
            $i ++; //计数器
            if($arr[$lower] == $num){
             return $lower;
            }
            if($arr[$high] == $num){
             return $high;
            }
            $middle = intval(($lower + $high) / 2);
            if($num < $arr[$middle]){
             $high = $middle - 1;
            }else if($num > $arr[$middle]){
             $lower = $middle + 1;
            }else{
             return $middle;
            }
           }
           //前往⑴表现查找失败
           return ⑴;
          }
          $arr = array(0,1,16,24,35,47,59,62,73,88,99);
          $pos = binsearch($arr,62);
          print($pos);
          echo "<br>";
          echo $i;
          
          

          运转后果:

          7
          3
          
          

          总结:

          2叉查找的工夫庞大度是 O(logn)。不外由于2叉查找的条件条件是需求有序表顺序存储(数组),假如该有序表需求频繁的履行拔出或删除操作,保护有序的排序会带来不小的任务量。

          更多关于PHP相干内容感兴味的读者可检查本站专题:《PHP数据构造与算法教程》、《php顺序设盘算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技能大全》、《PHP经常使用遍历算法与技能总结》及《PHP数学运算技能总结》

          希望本文所述对各人PHP顺序设计有所协助。