Using PHP to implement binary search algorithm code sharing

Using PHP to implement binary search algorithm code sharing_PHP tutorial

WBOY

Release： 2016-07-21 15:28:00

Original

905 people have browsed it

The first method:
[Binary search requirements]: 1. Must use sequential storage structure 2. Must be arranged in order according to keyword size.
【Advantages and Disadvantages】The advantages of the halved search method are fewer 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 two sub-tables, the first and last. If the middle position record If the recorded keyword is greater than the search keyword, then the previous subtable will be searched further, otherwise the next subtable will be searched further.

Copy code The code is as follows:

 
//Author: Distant Expectation
/ /QQ:15624575 
//Homepage: http://www.phptogether.com/ 
//Forward sorted array
$arr=array(1,3,5,7,9,11 ); 
//Reverse sorted array
$arr2=array(11,9,7,5,3,1); 
//Binary search for forward sorted array
function searchpart($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid= intval(($start+$end)/2);//Here you only need to ensure that the calculated value of the middle item subscript is an integer, or it can be rounded without affecting the result
if($arr[$mid]>$ x) {//If the value of the middle item is greater than the value to be checked, it means that the generation difference value is located to the left of the middle item. Therefore, the starting subscript remains unchanged, and the ending subscript becomes the middle item subscript minus 1. The first search If $arr[0]-$arr[5] is used, the next search will be 
$end=$mid-1;//$arr[0]-$arr[1] 
}elseif($arr [$mid]<$x){//If the value of the middle item is less than the value to be checked, it means that the generation difference value is located on the right side of the middle item. Therefore, the ending subscript remains unchanged and the starting subscript becomes the middle item subscript. Add 1, if the first search is $arr[0]-$arr[5], the next // search is, $arr[3]-$arr[5] 
$start=$mid+ 1; 
}else{//Found, return the subscript of the value to be searched 
return $mid; 
} 
} 
} 
//Bisection the reverse sorted array Search
function searchpart2($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);//Here you only need to ensure that the calculated value of the middle item subscript is an integer, or it can be rounded without affecting the result
if($arr[$ mid]>$x){//If the value of the middle item is greater than the value to be checked, it means that the generation difference value is located on the right side of the middle item. Therefore, the ending subscript remains unchanged and the starting subscript becomes the middle item subscript plus 1. , if the first search is $arr[0]-$arr[5], the next search will be 
$start=$mid+1;//$arr[3]-$arr[5] 
 }elseif($arr[$mid]<$x){//If the value of the middle item is less than the value to be checked, it means that the generation difference value is located to the left of the middle item. Therefore, the starting subscript remains unchanged and the ending subscript changes. The subscript of the middle term is reduced by 1. If the first search is $arr[0]-$arr[5], the next // search is, $arr[0]-$arr[1] 
$ end=$mid-1; 
}else{//Found, return the subscript of the value to be searched
return $mid; 
} 
} 
} 
echo searchpart2($ arr,5).'
'; 
echo searchpart2($arr2,5); 
?> 

PHP binary search algorithm implementation
Recently I have sorted out the algorithm knowledge I have learned before. Although algorithms are rarely used in WEB development, I still make a backup of some useful algorithms.
The binary 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] then find x , the algorithm terminates. If xa[n/2], then we only need to continue searching for x in the right half of the array a.
Binary search method is extremely widely used, and its idea is 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

Copy code The code is as follows:

 
/**
* Binary search algorithm
* 
* @param array $arr ordered array
* @param int $val the value to be searched for
* @return int the search value exists and returns the array subscript, Does not exist and returns -1 
*/ 
function binary_search($arr,$val) 
{ 
$l = count($arr);//Get the length of the ordered array
$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; 
} 
//Example
$arr = array(1,2,3,4,5,6,7,8,9,12,23,33,35,56, 67,89,99); 
echo binary_search($arr,57); 