二分查找

---

 

简介：

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。

算法要求：

1.必须采用顺序存储结构。2.必须按关键字大小有序排列。

 

时间复杂度：可以表示O(h)=O(log2n)（是以2为底，n的对数）

---

 

代码示例：

（考虑到数组索引可能从非0开始）

方式一：使用wile循环,

<?php function binary_search2($arr, $value) { $len = count($arr); $keys_arr = array_keys($arr);//获取所有的键 $min_key = $keys_arr[0];//获得最小的键 $max_key = $min_key + $len -1;//获得最大的键 while ($min_key <= $max_key) { $middle_key = intval(($min_key + $max_key) / 2); if ($value > $arr[$middle_key]) { $min_key = $middle_key + 1; } elseif ($value < $arr[$middle_key]) { $max_key = $middle_key - 1; } else { return $middle_key; } } return false; }

 

方式二：递归调用

<?php function binary_search($arr,$search){ $len = count($arr); $keys_arr = array_keys($arr);//获取所有的键 $min_key = $keys_arr[0];//获得最小的键 $max_key = $min_key + $len -1;//获得最大的键 if($search>$arr[$max_key] || $search<$arr[$min_key]){ return false; } $middle_key = intval(($min_key + $max_key ) / 2);//中间的键 $middle_len = intval($len / 2); if($arr[$middle_key] > $search){ $new_arr = array_slice($arr,0,$middle_len,true); return binary_search($new_arr,$search); }else if($arr[$middle_key] < $search){ $new_arr = array_slice($arr,$middle_len,$len,true); return binary_search($new_arr,$search); }else{ return $middle_key; } }

---

php相关函数：array_search();

array_search(value,array,strict)

---

 

转载于:https://www.cnblogs.com/gyfluck/p/10620365.html