设为首页收藏本站

PHPIN.NET

 找回密码
 立即注册
查看: 698|回复: 0

[基础知识] PHP二分算法查找的代码实现及详细分析

[复制链接]

374

主题

381

帖子

2558

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
2558
发表于 2015-1-19 22:26:25 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
PHP二分算法查找的代码实现及详细分析

PHP二分查找函数,Code:
  1. /**
  2. * 二分算法查找
  3. * @param array $array 要查找的数组
  4. * @param int $min_key 数组的最小下标
  5. * @param int $max_key 数组的最大下标
  6. * @param mixed $value 要查找的值
  7. * @return boolean
  8. */
  9. function bin_search($array,$min_key,$max_key,$value){
  10.     if($min_key <= $max_key){
  11.         $key = intval(($min_key+$max_key)/2);
  12.         if($array[$key] == $value){
  13.             return true;
  14.         }elseif($value < $array[$key]){
  15.             return bin_search($array,$min_key,$key-1,$value);
  16.         }else{
  17.             return bin_search($array,$key+1,$max_key,$value);
  18.        }
  19.     }else{
  20.         return false;
  21.     }
  22. }

  23. //现在我们来测试一下这个函数
  24. $array = array(1,22,23,45,58);
  25. $value = 45;
  26. $min_key = min(array_keys($array));
  27. $max_key = max(array_keys($array));
  28. if(bin_search($array,$min_key,$max_key,$value)){
  29.     echo "Search Success!";
  30. }else{
  31.     echo "Search Faliure!";
  32. }
复制代码

这样就实现了二分查找的功能了,是不是很简单呢?
这里涉及到了两个知识点:
首先是二分算法的概念:如下
1、二分查找的先决条件:就是表中结点按关键字有序,且顺序(一维数组)存储.
2、二分法思想:取中,比较
(2.1)求有序表的中间位置mid
(2.2)若r[mid].key == k,则查找成功,若r[mid].key > k,在左子表中继续进行二分查找;若r[mid].key < k,则在右字表中继续进行二分查找
然后就是 递归了,这个大家都比较熟悉,在此就不多说了。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|PHPIN.NET ( 冀ICP备00000001号 )|网站地图  

GMT+8, 2016-12-10 20:45

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表