Use PHP to implement binary search algorithm code sharing

Method 1:
[2 points search requirements] : 1. Must use the sequential storage structure 2. Must be arranged in order according to the size of the keyword.
[advantages and disadvantages] the advantages of the binary search method are less comparison times, fast search speed, good average performance; The disadvantage is that it requires the waiting table to be an ordered table, and it is difficult to insert and delete. Therefore, the binary search method is suitable for frequent ordered lists that do not change frequently.
[algorithm idea] first, compare the keywords of the position record in the middle of the table with the search keywords. If they are equal, the search will be successful. Otherwise, the middle position record is used to divide the table into two sub-tables. If the keyword of the middle position record is greater than the search keyword, the first sub-table will be searched one step ahead, otherwise, the second sub-table will be searched one step ahead.

 
<?php 
// Akik: distant expectations  
//QQ:15624575 
// Home page: http://www.phptogether.com/ 
// A forward-sorted array  
$arr=array(1,3,5,7,9,11); 
// Reverse sorted array  
$arr2=array(11,9,7,5,3,1); 
// To sort the array in the forward direction 2 searching  
function searchpart($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);// You just need to make sure that the index of the middle index is an integer, or you can 4 Give up 5 In, does not affect the result  
if($arr[$mid]>$x){// If the value of the middle term is greater than the value to be investigated, the Ming difference is to the left of the middle term. Therefore, the initial subscript remains the same, and the end subscript becomes the subscript of the middle term 1 In the first 1 The second search is for $arr[0]-$arr[5] Under the words, 1 searches  
$end=$mid-1;//$arr[0]-$arr[1] 
}elseif($arr[$mid]<$x){// If the value of the middle term is less than the value to be checked, the Ming difference is to the right of the middle term. Therefore, the ending subscript is unchanged, and the starting subscript becomes the middle term subscript plus 1 In the first 1 The second search is for $arr[0]-$arr[5] Under the words, 1// The sub-search is, $arr[3]-$arr[5] 
$start=$mid+1; 
}else{// Found, return the value of the subscript  
return $mid; 
} 
} 
} 
// I'm going to reverse sort the array 2 searching  
function searchpart2($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);// You just need to make sure that the index of the middle index is an integer, or you can 4 Give up 5 In, does not affect the result  
if($arr[$mid]>$x){// If the value of the middle term is greater than the value to be investigated, the difference of Ming dynasty is located to the right of the middle term. Therefore, the ending subscript is unchanged, and the starting subscript becomes the middle term subscript plus 1 In the first 1 The second search is for $arr[0]-$arr[5] Under the words, 1 searches  
$start=$mid+1;//$arr[3]-$arr[5] 
}elseif($arr[$mid]<$x){// If the value of the middle term is less than the value to be checked, the Ming difference is to the left of the middle term. Therefore, the initial subscript remains the same, and the ending subscript becomes the subscript of the middle term 1 In the first 1 The second search is for $arr[0]-$arr[5] Under the words, 1// The sub-search is, $arr[0]-$arr[1] 
$end=$mid-1; 
}else{// Found, return the value of the subscript  
return $mid; 
} 
} 
} 
echo searchpart2($arr,5).'<br>'; 
echo searchpart2($arr2,5); 
?> 

PHP 2 - point search algorithm implementation
Recently, I sorted out the algorithm knowledge I learned before. Although the algorithm used in the development of WEB was less, I still made a backup of some useful algorithms.
The binary search method is also known as the two-part search method. It makes full use of the order relationship between elements, adopts the divide-and-conquer strategy, and can complete the search task in the worst case using O(log n).
[basic idea]
Divide the n elements into two halves with roughly the same number. Compare a[n/2] with x. If x=a[n/2], x will be found and the algorithm will terminate. If x < If we have a[n/2], we simply continue to search for x in the left half of the array a (assuming the array elements are in ascending order). If x > a[n/2], we simply continue to search for x in the right half of the array a.
The two-point search method is widely used and its ideas are easy to understand. The first two-point search algorithm appeared as early as 1946, but the first completely correct two-point search algorithm did not appear until 1962. In his book Writing Correct Programs, Bentley writes that 90 percent of computer experts can't write the exact right two-point search algorithm in two hours. The key to the problem lies in the accurate formulation of the boundary of each search range and the determination of termination conditions, and the correct induction of all kinds of odd even cases. In fact, after sorting out, we can find its specific algorithm is very intuitive.
PHP 2 - point search algorithm implementation

 
/** 
* 2 Split search algorithm  
* 
* @param array $arr  Orderly array  
* @param int $val  Search value  
* @return int  The lookup value exists and returns an array subscript , Nonexistent return -1 
*/ 
function binary_search($arr,$val) 
{ 
$l = count($arr);// Get the ordered array length  
$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; 
} 
// The sample  
$arr = array(1,2,3,4,5,6,7,8,9,12,23,33,35,56,67,89,99); 
echo binary_search($arr,57);