Two implementation examples of PHP binary search_PHP tutorial

php binary search example

Commonly used writing methods for binary search are recursive and non-recursive. When looking for the median, the interpolation method can be used instead of the median method.
When the data in the ordered array increases uniformly, the interpolation method can be used to reduce the algorithm complexity from lgN of the median method to lglgN

Copy code The code is as follows:

/**
* Binary search recursive solution
* @param type $subject
* @param type $start
* @param type $end
* @param type $key
* @return boolean
*/
function binarySearch_r($subject, $ start, $end, $key)
{

if ( $start >= $end ) return FALSE;
$mid = getMidKey($subject, $start, $end, $key);
if ( $subject[$mid] == $key ) return $mid;
if ( $key > $subject[$mid] ) {
return binarySearch($subject, $mid, $end, $key);
}
if ( $key <= $subject[$mid] ) {
return binarySearch($subject, $start, $mid, $key);
}
}

/**
* Non-recursive algorithm for binary search
* @param type $subject
* @param type $n
* @param type $key
*/
function binarySearch_nr($subject, $n, $key)
{
$low = 0;
$high = $n;
while ( $low <= $high ) {
$mid = getMidKey($subject, $low, $high, $key);
if ( $subject[$mid] == $key ) return $ mid;
if ( $subject[$mid] < $key ) {
$low = $mid + 1;
}
if ( $subject[$mid] > $key ) {
$high = $mid - 1;
}
}
}
function getMidKey($subject, $low, $high, $key)
{
/ **
* Median algorithm 1 does not use the ($low+$high)/2 method to prevent overflow when low and high are large....
*/
//return round($low + ($high - $low) / 2);

/**
* The improved interpolation algorithm finds the median. When the numerical distribution is uniform, the algorithm complexity is reduced to lglgN
* Median algorithm 2
*/
return round( (($key - $subject[$low]) / ($subject[$high] - $subject[$low])*($high- $low) ) );
}

http://www.bkjia.com/PHPjc/740665.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/740665.htmlTechArticlephp binary search example Binary search commonly written methods are recursive and non-recursive. When looking for the median, you can use interpolation method instead of the median method. When the data in the ordered array increases uniformly,...