马富天PHP博客

二分搜索算法

学习笔记 马富天 2016-09-18 15:01:39 11 0

【摘要】算法课老师让我们用代码把书本上的二分搜索算法用代码编程实现,我就在这里做个小笔记。

二分搜索算法的基本思想是将 n 个元素分成大致相同的两半,取 a[n/2] 与 x 作比较。如果 x=a[n/2] ,则找到 x ,算法结束;如果 xa[n/2] ,则只在数组的右半部分继续搜索x。具体算法可以用PHP代码如下实现:

  1. //	编程实现脚本语言:PHP
  2. $arr = [1,3,4,5,8,10,12,20,23,29,88,119,129,200];	//	已按升序排好序的N个元素
  3. $n = 119;	//	要搜索的数
  4. function BinarySearch($arr,$n)
  5. {
  6. 	$left = 0;	//	初始化左半部搜索下标
  7. 	$right = count($arr) - 1;	//	初始化数组右半部下标
  8. 	while($left <= $right)
  9. 	{
  10. 		$mid = ceil(($left + $right) / 2);	//	中间元素下标
  11. 		if($n == $arr[$mid])	//	找到元素,返回数组下标
  12. 		{
  13. 			return $mid;
  14. 		}
  15. 		if($n < $arr[$mid])	//	$n在数组的左半部
  16. 		{
  17. 			$right = $mid - 1;
  18. 		}else
  19. 		{
  20. 			//	$n在数组的右半部分
  21. 			$left = $mid + 1;
  22. 		}
  23. 	}
  24. 	return -1;
  25. }
  26. echo BinarySearch($arr,$n);	// 输出11,下标是第11个

版权归 马富天PHP博客 所有

本文标题:《二分搜索算法》

本文链接地址:http://www.mafutian.net/203.html

转载请务必注明出处,小生将不胜感激,谢谢! 喜欢本文或觉得本文对您有帮助,请分享给您的朋友 ^_^

0

0

上一篇《 phpMyAdmin - 错误 您应升级到 MySQL 5.5.0 或更高版本。 》 下一篇《 PHP去除字符串中的最后一个字符的三种方法 》
分享到:

暂无评论

评论审核未开启
表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情
验证码