• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

php二分查找

开发技术 开发技术 4天前 7次浏览
 1 <?php
 2 
 3 function binarySearch($arr,$findMe)
 4 {
 5     if(0 == ($cnt = count($arr))){
 6         return -1;
 7     }
 8     $startIndex = 0;
 9     $endIndex = $cnt - 1;
10 
11     while($startIndex <= $endIndex){
12         /**
13          * 直观的写法 
14          * $mid = floor($startIndex + ($endIndex - $startIndex) / 2);
15          */
16         /**
17          * 下面的写法我一下子还不明白咋回事。。
18          * 证明:
19          * 设:起始位置x,结束位置为y。则中间:
20          * x + (y - x)/2 = mid;
21          * 2x + (y - x) = 2mid;
22          * x + y = 2mid;
23          * (x + y) / 2 = mid;
24          */ 
25         $mid = floor(($endIndex + $startIndex) / 2);
26         if($arr[$mid] == $findMe){
27             return $mid;
28         } 
29         if($arr[$mid] > $findMe ){
30             $endIndex = $mid - 1;
31         }elseif($arr[$mid] < $findMe) {
32             $startIndex = $mid + 1;
33         }
34     }
35     return -1;
36 }
37 $datas = array(1,2,3,4,5,6,7,8,9,10,11);
38 $foundedIndex = binarySearch($datas,'7');
39 var_dump($foundedIndex);

 


程序员灯塔
转载请注明原文链接:https://www.wangt.cc/2020/11/php%e4%ba%8c%e5%88%86%e6%9f%a5%e6%89%be/
喜欢 (0)