PHP implementation of binary search example code

Binary search Also known as half search, the advantage is that the number of comparisons is less, the search speed is fast, and the average performance is good; its disadvantage is that the table to be looked up is required to be an ordered table, and insertionDeletiondifficulty. Therefore, the binary search method is suitable for ordered lists that do not change frequently but are searched frequently. First, assuming that the elements in the table are arranged in ascending order, 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 If the keyword recorded in the middle position is greater than the search keyword, then the previous sub-table will be searched further, otherwise the next sub-table will be searched further. Repeat the above process until a record that meets the conditions is found, making the search successful, or until the subtable does not exist, in which case the search fails.

Loop

function binary(&$arr,$low,$top,$target){
    while($low <= $top){        $mid = floor(($low+$top)/2);        echo $mid."<br>";        if($arr[$mid]==$target){            return $arr[$mid];
        }elseif($arr[$mid]<$target){            $low = $mid+1;                
        }else{            $top = $mid-1;
        }
    }    return -1;
}

Recursion

function binaryRecursive(&$arr,$low,$top,$target){
    if($low<=$top){        $mid = floor(($low+$top)/2);        if($mid==$target){            return $arr[$mid];
        }elseif($arr[$mid]<$target){            return binaryRecursive($arr,$mid+1,$top,$target);
        }else{            return binaryRecursive($arr,$low,$top-1,$target);
        }
    }else{        return -1;
    }
}

Note: The premise of binary search is that the array is ordered arrangement

The above is the detailed content of PHP implementation of binary search example code. For more information, please follow other related articles on the PHP Chinese website!