首页 > 代码库 > 二分查找
二分查找
二分查找查找元素,效率很高,时间复杂度是O(log2n);但是前提是数组必须是有序的数组。
1.先取到数组的中间值,然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作;若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作
2重复第二步操作直至找出目标数字
比如从1,3,9,23,54 中查找数字23,
首位置为0, 尾位置为4,中间位置就为2 值为9,比23小,则首位置更新为2+1即3;那么接下来中间位置就为(3+4)/2=3,值为23,比较相等即找到
二分查找递归方法
public function 二分查找($arr, $start, $stop, $num) { if ($start > $stop) return false; //二分查找(递归) $mid = floor(($start + $stop) / 2); if ($arr[$mid] == $num) { return $mid; } elseif ($arr[$mid] > $num) { return $this->二分查找($arr, $start, $mid - 1, $num); } elseif ($arr[$mid] < $num) { return $this->二分查找($arr, $mid + 1, $stop, $num); } }
二分查找迭代方法
public function 二分查找($arr,$num) { //二分查找(迭代) $start=0; $stop=count($arr)-1; while($start<=$stop){ $mid=floor(($stop+$start)/2); if($arr[$mid]==$num){ return $mid; }elseif ($arr[$mid]>$num){ $stop=$mid-1; }elseif ($arr[$mid]<$num){ $start=$mid+1; } } return false; }
二分查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。