Using PHP to implement binary search algorithm code sharing

The first method:
[Binary search requirements]: 1. A sequential storage structure must be used 2. It must be arranged in order according to the size of the keywords.
【Advantages and Disadvantages】The advantages of the halved search method are less number of comparisons, fast search speed, and good average performance; its disadvantage is that the table to be looked up is required to be an ordered table, and insertion and deletion are difficult. Therefore, the binary search method is suitable for ordered lists that do not change frequently but are searched frequently.
[Algorithm idea] First, compare the keyword recorded in the middle position of the table with the search keyword. If the two are equal, the search is successful; otherwise, use the middle position record to divide the table into the front and last sub-tables. If the middle position record is If the keyword is greater than the search keyword, then the previous subtable will be searched further, otherwise the next subtable will be searched further.

$x){//如果中间项的值大于待查值，说明代差值位于中间项的左边，因此，起始下标不变，结束下标变成中间项下标减1，第一次搜索的是$arr[0]-$arr[5]的话，下一次搜索 $end=$mid-1;//$arr[0]-$arr[1] }elseif($arr[$mid]<$x){//如果中间项的值小于待查值，说明代差值位于中间项的右边，因此，结束下标不变，起始下标变成中间项下标加1，第一次搜索的是$arr[0]-$arr[5]的话，下一//次搜索是，$arr[3]-$arr[5] $start=$mid+1; }else{//找到了，返回待查值下标 return $mid; } } } //对逆向排序的数组进行二分查找 function searchpart2($arr,$x){ $start=0; $end=count($arr)-1; while($start<=$end){ $mid=intval(($start+$end)/2);//这里只需要保证中间项下标的计算值为整数即可，也可以四舍五入，不影响结果 if($arr[$mid]>$x){//如果中间项的值大于待查值，说明代差值位于中间项的右边，因此，结束下标不变，起始下标变成中间项下标加1，第一次搜索的是$arr[0]-$arr[5]的话，下一次搜索 $start=$mid+1;//$arr[3]-$arr[5] }elseif($arr[$mid]<$x){//如果中间项的值小于待查值，说明代差值位于中间项的左边，因此，起始下标不变，结束下标变成中间项下标减1，第一次搜索的是$arr[0]-$arr[5]的话，下一//次搜索是，$arr[0]-$arr[1] $end=$mid-1; }else{//找到了，返回待查值下标 return $mid; } } } echo searchpart2($arr,5).'
'; echo searchpart2($arr2,5); ?>

Binary search algorithm implementation in PHP
Recently sorted out the algorithm knowledge I learned before. Although the algorithm is rarely used in WEB development, I still make a backup of some useful algorithms.
The half-search method is also called the binary search method. It makes full use of the order relationship between elements and adopts the divide-and-conquer strategy. It can complete the search task in O(log n) in the worst case.
[Basic idea]
Divide n elements into two halves with roughly the same number, compare a[n/2] with the x you want to find, if x=a[n/2], find x, and the algorithm terminates. If x a[n/2], then we only need to continue searching for x in the right half of the array a.
The binary search method is extremely widely used, and its ideas are easy to understand. The first binary search algorithm appeared as early as 1946, but the first completely correct binary search algorithm did not appear until 1962. Bentley wrote in his book "Writing Correct Programs" that 90% of computer experts cannot write a completely correct binary search algorithm within 2 hours. The key to the problem is to accurately formulate the boundaries of each search range and determine the termination conditions, and correctly summarize the various situations of odd and even numbers. In fact, after sorting it out, we can find that its specific algorithm is very intuitive.
Binary search algorithm implementation in PHP

/** * 二分查找算法 * * @param array $arr 有序数组 * @param int $val 查找的数值 * @return int 查找值存在返回数组下标,不存在返回-1 */ function binary_search($arr,$val) { $l = count($arr);//获得有序数组长度 $low = 0; $high = $l -1; while($low <= $high) { $middle = floor(($low + $high) / 2); if($arr[$middle] == $val) { return $middle; } elseif($arr[$middle] > $val) { $high = $middle - 1; } else { $low = $middle + 1; } } return -1; } //示例 $arr = array(1,2,3,4,5,6,7,8,9,12,23,33,35,56,67,89,99); echo binary_search($arr,57);

For more code sharing using PHP to implement binary search algorithm, please pay attention to the PHP Chinese website!