当前位置:首页 > PHP教程 > php应用 > 列表

PHP实现二分查找算法(代码详解)

发布:smiling 来源: PHP粉丝网  添加日期:2020-04-14 16:31:56 浏览: 评论:0 

二分查找又称折半查找,二分查找算法要求数据必须是有序的,以下是php实现二分查找算法的代码。

一:递归方式

  1. $array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89]; 
  2.  
  3. $target = 73; 
  4.  
  5. $low = 0; 
  6.  
  7. $high = count($array)-1; 
  8.  
  9. function bin_search($array$low$high$target){ 
  10.  
  11.     if ( $low <= $high){ 
  12.  
  13.         var_dump($low$high);echo "\n"
  14.  
  15.         $mid =  intval(($low+$high)/2 ); 
  16.  
  17.         if ($array[$mid] ==  $target){ 
  18.  
  19.             return true; 
  20.  
  21.         }elseif ( $target < $array[$mid]){ 
  22.  
  23.             return  bin_search($array$low,  $mid-1, $target); 
  24.  
  25.         }else
  26.  
  27.             return  bin_search($array$mid+ 1, $high$target); 
  28.  
  29.         } 
  30.  
  31.     } 
  32.  
  33.     return false; 
  34.  
  35.  
  36. $find = bin_search($array$low$high$target); 
  37.  
  38. var_dump($find); 

执行结果

  1. int(0) 
  2.  
  3. int(25) 
  4.  
  5. int(13) 
  6.  
  7. int(25) 
  8.  
  9. int(20) 
  10.  
  11. int(25) 
  12.  
  13. int(20) 
  14.  
  15. int(21) 
  16.  
  17. bool(true) 

我们看到,经过4次二分查找,查找区间不断折半,最终找到了$target。

二:循环方式

  1. $array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89]; 
  2.  
  3. $target = 73; 
  4.  
  5. function bin_search($array$target
  6.  
  7.  
  8.     $low = 0; 
  9.  
  10.     $high = count($array)-1; 
  11.  
  12.     $find = false; 
  13.  
  14.     while (true){ 
  15.  
  16.         if ($low <= $high){ 
  17.  
  18.             var_dump($low$high);echo "\n"
  19.  
  20.             $mid = intval(($low + $high)/2); 
  21.  
  22.             if ($array[$mid] == $target){ 
  23.  
  24.                 $find = true; 
  25.  
  26.                 break
  27.  
  28.             } elseif ($array[$mid] < $target){ 
  29.  
  30.                 $low = $mid+1; 
  31.  
  32.             } elseif ($array[$mid] > $target){ 
  33.  
  34.                 $high = $mid-1; 
  35.  
  36.             } 
  37.  
  38.         } else { 
  39.  
  40.             break
  41.  
  42.         } 
  43.  
  44.     } 
  45.  
  46.     return $find
  47.  
  48.  
  49. $find = bin_search($array$target); 
  50.  
  51. var_dump($find); 

执行结果

  1. int(0) 
  2.  
  3. int(25) 
  4.  
  5. int(13) 
  6.  
  7. int(25) 
  8.  
  9. int(20) 
  10.  
  11. int(25) 
  12.  
  13. int(20) 
  14.  
  15. int(21) 
  16.  
  17. bool(true) 

我们看到,两种方式过程和结果相同。下面我们来测试下针对关联数组的二分查找算法:

  1. $array = ['a'=>1,'b'=>3,'c'=>6,'d'=>9,'e'=>13,'f'=>18,'g'=>19,'h'=>29,'i'=>38]; 
  2.  
  3. $target = 19; 
  4.  
  5. function bin_search($array$target
  6.  
  7.  
  8.     $low = 0; 
  9.  
  10.     $high = count($array)-1; 
  11.  
  12.     $key_map = array_keys($array); 
  13.  
  14.     $find = false; 
  15.  
  16.     while (true){ 
  17.  
  18.         if ($low <= $high){ 
  19.  
  20.             var_dump($low$high);echo "\n"
  21.  
  22.             $mid = intval(($low + $high)/2); 
  23.  
  24.             if ($array[$key_map[$mid]] == $target){ 
  25.  
  26.                 $find = true; 
  27.  
  28.                 break
  29.  
  30.             } elseif ($array[$key_map[$mid]] < $target){ 
  31.  
  32.                 $low = $mid+1; 
  33.  
  34.             } elseif ($array[$key_map[$mid]] > $target){ 
  35.  
  36.                 $high = $mid-1; 
  37.  
  38.             } 
  39.  
  40.         } else { 
  41.  
  42.             break
  43.  
  44.         } 
  45. //phpfensi.com 
  46.     } 
  47.  
  48.     return $find
  49.  
  50.  
  51. $find = bin_search($array$target); 
  52.  
  53. var_dump($find); 

执行结果

  1. int(0) 
  2.  
  3. int(8) 
  4.  
  5. int(5) 
  6.  
  7. int(8) 
  8.  
  9. bool(true) 

两次二分查找,找到了$target,针对关联数组,我们使用了php的array_keys函数获得这个关联有序数组的key,通过key间接比对$target和$array的值。

Tags: PHP查找算法

分享到: