Binary Search Algorithm

Posted on

Binary search in a method of searching an array using the divide and conquer technique. It only works on an array that was been sorted ascendingly and works by splitting the array into two down the middle, calculating whether the middle value of the array is greater or less then the key, it then picks the correct side of the split and the process is done again until the middle value equals the searched for value.

The steps are found below;

  • The array is [1,4,7,9,12,15,16,24,35,57]
  • the low value is 1
  • The high value is 57
  • The key that I am looking for is 24
  1. Find the middle item in the array in between high and low.
  2. If the middle number equals the key stop, You have found it!
  3. Work out whether the key is higher or lower than the middle value.
  4. If lower set the high value to be the middle
  5. If higher set the low value to be the middle
  6. Go back to step 2

That is basically it, and now for the code.

function binary_search(array $arr, $value, $min, $max) {
    $middle = 0;

    // Search until there are no more elements to check
    // The loop is terminated if the value is found
    while ($max >= $min) {
        // Calculate the mid point of the set
        $middle = ceil((($min + $max) / 2));

        // Check if the key is potentially in the lower subset
        if ($middle === $value) {
            // Search the lower subset for the key
            $max = $middle - 1;
        }

        // Check if the key is potentially in the upper subset
        else if ($arr[$middle] < $value) {
            // Search the upper subset for the key
            $min = $middle + 1;
        }

        else {
            // Value found. Return it and terminate loop
            return $middle;
        }
    }

    return false; // Value not found
}

$arr = [1,4,7,9,12,15,16,24,35,57]; // array to search
$result = binary_search($arr, 57, 0, (count($arr) - 1));

// returns the index in which to the key resides
var_dump($result);