www.adminn.cn
站长正能量分享网!

php二分查找二种实现示例

AD:阿里云服务器企业会员更优惠 腾讯云香港,韩国免备案服务器1.8折优惠

这篇文章主要介绍了php二分查找的二种实现示例,递归解法二分查找和非递归算法二分查找的示例,需要的朋友可以参考下。

php二分查找示例

二分查找常用写法有递归和非递归,在寻找中值的时候,可以用插值法代替求中值法。

当有序数组中的数据均匀递增时,采用插值方法可以将算法复杂度从中值法的lgN减小到lglgN,代码如下:

  1. /** 
  2.  * 二分查找递归解法 
  3.  * @param type $subject 
  4.  * @param type $start 
  5.  * @param type $end 
  6.  * @param type $key 
  7.  * @return boolean 
  8.  */ 
  9. function binarySearch_r($subject$start$end$key
  10.  
  11.  if ( $start >= $end ) return FALSE; 
  12.  $mid = getMidKey($subject$start$end$key); 
  13.  if ( $subject[$mid] == $key ) return $mid
  14.  if ( $key > $subject[$mid] ) { 
  15.   return binarySearch($subject$mid$end$key); 
  16.  } 
  17.  if ( $key <= $subject[$mid] ) { 
  18.   return binarySearch($subject$start$mid$key); 
  19.  } 
  20.  
  21. /** 
  22.  * 二分查找的非递归算法 
  23.  * @param type $subject 
  24.  * @param type $n 
  25.  * @param type $key 
  26.  */ 
  27. function binarySearch_nr($subject$n$key
  28.  $low = 0; 
  29.  $high = $n
  30.  while ( $low <= $high ) { 
  31.   $mid = getMidKey($subject$low$high$key); 
  32.   if ( $subject[$mid] == $key ) return $mid
  33.   if ( $subject[$mid] < $key ) { 
  34.    $low = $mid + 1; 
  35.   } 
  36.   if ( $subject[$mid] > $key ) { 
  37.    $high = $mid – 1; 
  38.   } 
  39.  } 
  40. function getMidKey($subject$low$high$key
  41.  /** 
  42.   * 取中值算法1 取中值 不用 ($low+$high)/2的方式是因为 防止low和high较大时候,产生溢出…. 
  43.   */ 
  44.  //return round($low + ($high – $low) / 2); 
  45. //phpfensi.com 
  46.  /** 
  47.   * 经过改进的插值算法求中值,当数值分布均匀情况下,再降低算法复杂度到lglgN 
  48.   * 取中值算法2 
  49.   */ 
  50.  return round( (($key – $subject[$low]) / ($subject[$high] – $subject[$low])*($high$low) ) ); 

模板优惠价: (点击购买)
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《php二分查找二种实现示例》
文章链接:https://www.adminn.cn/news/8569.html
本站资源模板仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。2021.5月起,网站调整,暂不再分享免费模板。谢谢理解

扫码支付后请联系右侧QQ发送下载地址!!

源码请勿用于任何涉灰站点!净化网络,站长更有责!

支付宝扫一扫打赏