十大编程算法之一二分查找算法
二分查找的基本思想是：将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜 素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组 为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
<?php /** * * @author LiZeQiao <674531003@qq.com> * @version $Id: index.php $ * @site http://www.phperblog.cn */ function binsearch($x,$arr){ $c=count($arr); $lower=0; $high=$c-1; while($lower<=$high){ $middle=intval(($lower+$high)/2); if($arr[$middle]>$x){ $high=$middle-1; }elseif($arr[$middle]<$x){ $lower=$middle+1; }else{ return $middle; } } return false; } ?> |
结果：
|
1 2 3 4 5 |
$arr=array();$x=222; $arr=array( 3,5,7,88,145,222,333,4567,17023,29456, ); var_dump(binsearch($x,$arr)); |
|
1 |
int 5 |
请尊重我们的辛苦付出，未经允许，请不要转载 本站 的文章，鄙视各种无耻的采集行为！