PHP二分查找算法的实现方法示例

php  /  管理员 发布于 7年前   119

本文实例讲述了PHP二分查找算法的实现方法。分享给大家供大家参考，具体如下：

二分查找法需要数组是一个有序的数组

假设我们的数组是一个递增的数组，首先我们需要找到数组的中间位置.

1. 要知道中间位置就需要知道起始位置和结束位置，然后取出中间位置的值来和我们的值做对比。

2. 如果中间值大于我们的给定值，说明我们的值在中间位置之前，此时需要再次二分，因为在中间之前，所以我们需要变的值是结束位置的值，此时结束位置的值应该是我们此时的中间位置。

3. 反之，如果中间值小于我们给定的值，那么说明给定值在中间位置之后，此时需要再次将后一部分的值进行二分，因为在中间值之后，所以我们需要改变的值是开始位置的值，此时开始位置的值应该是我们此时的中间位置，直到我们找到指定值。

4. 或者中间值等于最初的起始位置，或结束位置（此时说明给定值未找到），下面我们来用代码实现~

//循环实现function getValue($num,$arr){  //查找数组的中间位置  $length=count($arr);  $start=0;  $end=$length;  $middle=floor(($start+$end)/2);  //循环判断  while($start>$end-1)  {    if($arr[middle]==$num)    {      return middle+1;    } elseif($arr[middle]<$num)    {      //如果当前要查找的值比当前数组的中间值还要打，那么意味着该值在数组的后半段      //所以起始位置变成当前的middle的值，end位置不变。      $start=$middle;      $middle=floor(($start+$end)/2);    } else{      //反之      $end=$middle;      $middle=floor(($start+$end)/2);    }  }  return false;}

//递归实现/** 从数组中获取元素值* @param1 int $num，要查找的目标值* @param2 array $arr，要查找的数组* @param3 int $start，查找的起始位置* @param4 int $end，查找的结束位置* @return mixed，找到了返回位置，没找到返回false*/function getValue4($num,$arr,$start = 0,$end = 100){    //采用二分法查找    $middle = floor(($end + $start) / 2);    //判断    if($arr[$middle] == $num){      //已经找到了，递归的出口      return $middle + 1;    }elseif($arr[$middle] < $num){      //要查找的元素在数组的后半段      $start = $middle + 1;      //边界值      if($start >= $end){        //没有找到，但是已经超出边界值，递归出口        return false;      }      //调用自己去查找：递归点      return getValue4($num,$arr,$start,$end);  //getValue4($num,$arr,51,100)    }else{      //要查找的元素在数组的前半段      $end = $middle - 1;      //判断边界值      if($end < 0)return false;      //调用自己：递归点      return getValue4($num,$arr,$start,$end);  //getValue4($num,$arr,0,49)    }    //都没有找到    return false;}

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》及《php查找技巧与方法总结》

希望本文所述对大家PHP程序设计有所帮助。

您可能感兴趣的文章:

• PHP有序表查找之二分查找（折半查找）算法示例
• PHP实现的二分查找算法实例分析
• php实现的二分查找算法示例
• php顺序查找和二分查找示例
• PHP查找一列有序数组是否包含某值的方法