Binary Search Algorithm

by Devansh


Posted on 23 Oct 2018 11:10:19 (1 month ago)




Binary search algorithm divides the data set to find the match starting from the middle and it has only one recommendation i.e. data set should be in order. I am using PHP to explain the binary search below are the two sample functions one is simple binary seach and the other one is recursive binary search.

function binarySimpleSearch(array $numbers, int $needle): bool { 
    $low = 0;
    $high = count($numbers) - 1;
    while ($low <= $high) {
      $mid = (int) (($low + $high) / 2);
      if ($numbers[$mid] > $needle) {
        $high = $mid - 1;
      } else if ($numbers[$mid] < $needle) {
        $low = $mid + 1;
      } else {
        return TRUE;
      }
    }
    return FALSE;
}
function binaryRecursiveSearch(array $numbers, int $needle, int $low, int $high): bool {
    if ($high < $low) {
    	return FALSE;
    }
    $mid = (int) (($low + $high) / 2);
    if ($numbers[$mid] > $needle) {
      return binaryRecursiveSearch($numbers, $needle, $low, $mid - 1);
    } else if ($numbers[$mid] < $needle) {
      return binaryRecursiveSearch($numbers, $needle, $mid + 1, $high);
    } else {
      return TRUE;
    }
}

Now, testing above two functions.

$arr = [1, 5, 6, 9, 11, 21, 25, 32, 36, 56, 68, 70, 79, 88, 91, 94, 100];
var_dump(binarySimpleSearch($arr, 11)); // bool(true)
var_dump(binaryRecursiveSearch($arr, 11, 0, count($arr)-1)); // bool(true)