PHP 二分法查找数据

  作者:会飞的

不论在PHP中还是在其他的编程语言中,使用顺序法查找数据都面临着一个很大的问题,那就是:如果数组中的数据很多时,该怎么办?继续使用顺序法查找数据会使得PHP的效率变低。这时我们引入了二分法查找数据。二分法就是在PHP的数组中假象数组排好序了,然后通过对数组元素的比较得到结果。比较

不论在PHP中还是在其他的编程语言中,使用顺序法查找数据都面临着一个很大的问题,那就是:如果数组中的数据很多时,该怎么办?


继续使用顺序法查找数据会使得PHP的效率变低。


这时我们引入了二分法查找数据。


二分法就是在PHP的数组中假象数组排好序了,然后通过对数组元素的比较得到结果。比较一次就会排出1/2的数组。


例如:


<?php


  //函数名称为Dichotomy,$php为数组,$k为要查找的值,$low为最小的值,$max为最大值


  function Dichotomy($php,$k,$low,$max)


  {


    if(count($php)!= 0 and $max == 0)


    {


        $max = count($php);


    }


    if($low <= $max)


    {


    $mid = intval(($low+$max)/2);


    if($php[$mid] == $k)


    {


        return $mid;


    }


    else if($k < $php[$mid])


    {


        return Dichotomy($php,$k,$low,$mid-1);


    }


    else


    {


        return Dichotomy($php,$k,$mid+1,$max);


    }


    }


    return -1;


  }


  $php = array('1','2','3','4','5','6');


  echo Dichotomy($php,5);


?>

结果:

Warning: Missing argument 3 for Dichotomy(), called in E:xampphtdocsphpTest8.5.2.php on line 29 and defined in E:xampphtdocsphpTest8.5.2.php on line 3


Warning: Missing argument 4 for Dichotomy(), called in E:xampphtdocsphpTest8.5.2.php on line 29 and defined in E:xampphtdocsphpTest8.5.2.php on line 3

4


这是我第一次做的时候呈现的错误。问题出在哪里呢?


好吧:新手问题。因为在函数刚开始没有给$low和$max赋值,使得函数的if没有办法进行。


正确的代码如下:


<?php


  //函数名称为Dichotomy,$php为数组,$k为要查找的值,$low为最小的值,$max为最大值


  function Dichotomy($php,$k,$low=0,$max=0)


  {


    if(count($php)!= 0 and $max == 0)


    {


        $max = count($php);


    }


    if($low <= $max)


    {


    $mid = intval(($low+$max)/2);


    if($php[$mid] == $k)


    {


        return $mid;


    }


    else if($k < $php[$mid])


    {


        return Dichotomy($php,$k,$low,$mid-1);


    }


    else


    {


        return Dichotomy($php,$k,$mid+1,$max);


    }


    }


    return -1;


  }


  $php = array('1','2','3','4','5','6');


  echo Dichotomy($php,5);


?>

结果是:


4


返回的是键值。


这个PHP例子说的是在已知数组排序的情况和所需要查找的数据下所进行的:将数组中的最小和最大值相加取平均,因为已经知道所要查找的元素了,就比如我这个例子,所以从$mid+1到$max开始查找。


这样我们会想:天下哪里有这么便宜的事,谁实现知道所有的数组呢。所以,这种方法也不是很方便。


那么,你有什么建议呢?