A binary search divides a range of values into halves, and continues to narrow down the field of search until the unknown value is found.

As an analogy, consider the children's game "guess a number." The host has a secret number, and will only tell the player if their guessed number is higher than, lower than, or equal to the secret number. The player then uses this information to guess a new number.

As the player, one normally would start by choosing the range's midpoint as the guess, and then asking whether the guess was higher, lower, or equal to the secret number. If the guess was too high, one would select the point exactly between the range midpoint and the beginning of the range. If the original guess was too low, one would ask about the point exactly between the range midpoint and the end of the range. This process repeats until one has reached the secret number.

This is an example of a binary search.

Task

Given the starting point of a range, the ending point of a range, and the "secret value", implement a binary search.

Examples

PHP

loop

This approach uses a loop.

function binary_search( $secret, $start, $end )
{
        do
        {
                $guess = $start + ( ( $end - $start ) / 2 );

                if ( $guess > $secret )
                        $end = $guess;

                if ( $guess < $secret )
                        $start = $guess;

        } while ( $guess != $secret );

        return $guess;
}

recursion

This approach uses recursion.

function binary_search( $secret, $start, $end )
{
        $guess = $start + ( ( $end - $start ) / 2 );

        if ( $guess > $secret )
                return (binary_search( $secret, $start, $guess ));

        if ( $guess < $secret )
                return (binary_search( $secret, $guess, $end ) );

        return $guess;
}