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开始查找。

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

那么，你有什么建议呢？

猜你喜欢