返回顶部

收藏

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. 博主 发表 2013-05-25 00:00:00 PHP二维数组排序算法
  2. 博主 发表 2013-05-26 00:00:00 PHP数组排序算法整理
  3. libi 发表 2015-05-03 15:39:13 C语言基础:选择排序及冒泡排序算法
  4. alexzhou 发表 2013-01-10 06:10:38 [常用算法PHP实现]之奇偶排序
  5. Lok 发表 2017-09-27 03:36:18 一个菜单分类的算法(非递归)
  6. kaixinfelix 发表 2015-02-05 08:31:04 Php7新的哈希表实现
  7. furion 发表 2015-12-13 16:13:51 codility之GenomicRangeQuery
  8. alexzhou 发表 2013-01-10 09:07:52 [常用算法PHP实现]之鸡尾酒排序
  9. 胡 志伟 发表 2015-11-19 06:42:21 php实现dota天梯、wow竞技场、lol排位赛匹配加分算法ELO
  10. alexzhou 发表 2013-01-10 09:22:49 排序算法的分类
  11. alexzhou 发表 2013-01-11 11:13:42 [常用算法PHP实现]之选择排序
  12. bandit 发表 2015-01-06 09:01:50 排序算法PHP实现[下]

发表评论