返回顶部

收藏

PHP实现二分查找算法(折半算法)

更多
<?php
/**
 * 比较函数
 * @param scalar $var1
 * @param scalar $var2
 * return bool
 */
 function compare($var1,$var2)
 {
    if($var1>$var2)
    {
        return 1;
    }
    elseif($var1==$var2)
    {
        return 0;
    }
    else
    {
        return -1;
    }
 }

/**
 * 二分查找 重构的代码 支持关联数组
 * return index 查找目标数字所在的索引
 */
function binsearch_2($var=array(),$searchnum,$type=true)
{
    reset($var);
    $key=key($var);
    while($key!==null)                          //$key可能为0  所以要用!==null判断
    {
        $_map[]=$key;                           //键值映射
        next($var);
        $key=key($var);
    }
    echo '<pre>';
    print_r($_map);
    $left_border = 0;
    $right_border = count($_map)-1;
    while($left_border<=$right_border)
    {
        $middle=intval(($left_border+$right_border)/2);
        switch(compare($var[$_map[$middle]],$searchnum))
        {
            case -1:
                if($type)
                {
                    $left_border = $middle+1;
                }
                else
                {
                    $right_border = $middle-1;
                }
                break;
            case 0:
                return $_map[$middle];
            case 1:
                if($type)
                {
                    $right_border = $middle-1;
                }
                else
                {
                    $left_border = $middle+1;
                }
                break;
        }
    }
    echo '没有匹配项';
    return false;
}

$arr=array('a'=>1,2,3,4,5,6,7,'b'=>8,9,10,11,'c'=>12);
$index = binsearch_2($arr,12,true);
echo $index;
echo $arr[$index];
?>
//该片段来自于http://outofmemory.cn

标签:php,算法

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. 先为乱步 发表 2015-05-17 17:19:00 经典排序算法的PHP实现
  2. TLHL28 发表 2011-05-23 03:20:37 triple_des(des3) 算法 - php,python 实现
  3. furion 发表 2015-11-23 15:40:44 codility之MissingInteger
  4. damon 发表 2015-11-25 07:32:13 php中奖抽奖概率算法
  5. Rebill 发表 2013-06-16 08:23:23 PHP的Hash算法:Times33
  6. jed <jed521@163.com> 发表 2018-03-14 02:34:52 威盾PHP加密专家解密算法
  7. furion 发表 2015-04-28 17:02:36 codility之TapeEquilibrium
  8. damon 发表 2015-05-12 06:57:10 php函数array_multisort 和 uasort为数组排序的区别
  9. 博主 发表 2013-05-25 00:00:00 PHP二维数组排序算法
  10. 博主 发表 2013-05-26 00:00:00 PHP数组排序算法整理
  11. furion 发表 2015-12-13 16:13:51 codility之GenomicRangeQuery
  12. alexzhou 发表 2013-01-10 06:10:38 [常用算法PHP实现]之奇偶排序

发表评论