Binary search in PHP

PHP

Examples:
Input: 1 2 3 4 5 5 Output: 5 Exists Input: 1 5 8 0 Output: 0 Doesnt Exist
This search method is more more efficient than linear search.Method 1 (iterative) :Steps included:
1) Sort the array as binary search works only in sorted ranges
2) Calculate the middle element if the element we want to find is larger than the middle element search on the right, otherwise the search is on the left. 
3) Return True if the element is found. function binarySearch (Array $arr , $x ) { // check for empty array if ( count ( $arr ) === 0) return false; $low = 0; $high = count ( $arr ) - one; while ( $low < = $high ) {   // calculate the average index $mid = floor (( $low + $high ) / 2); // element found in the middle if ( $arr [ $mid ] == $x ) { return true; } if ( $x < $arr [ $mid ]) { // looking for the left side of the array $high = $mid - 1; } else { // search for the right side of the array $low = $mid + 1; } } // If we reach here, the x element does not exist return false; }  
// Driver code $arr = array (1, 2, 3, 4, 5); $value = 5; if (binarySearch ( $arr , $value ) == true) { echo $value . " Exists " ; } else { echo $value . "Doesnt Exist" ; }
?>
Exit:
5 Exists 
Method 2 (recursive):
Recursion - it is a way in which we repeatedly call the same function until a base condition is found to terminate the recursion. 
Continuing the steps in Method 1 here, we use the same idea, just recursively changing the function parameters and solving the problem. function binarySearch (Array $arr , $start , $end , $x ) { if ( $end < $start ) return false; $mid = floor (( $end + $start ) / 2 ); if ( $arr [ $mid ] == $x ) return true; elseif ( $arr [ $mid ] > $x ) { // call binarySearch at [start, mid - 1] return binarySearch ( $arr , $start , $mid - 1, $x ); } else { // call binarySearch on [mid + 1, end] return binarySearch ( $arr , $mid + 1, $end , $x ) ; } }  
// Driver code $arr = array (1, 2, 3, 4, 5); $value = 5; if (binarySearch ( $arr , 0, count ( $arr ) - 1, $value ) == true ) { echo $value . "Exists" ; } else { echo $value . "Doesnt Exist" ; } Exit:
5 Exists
Related PHP Functions:

in_array() in PHP

array_key_exists() in PHP



Get Solution for free from DataCamp guru