findNumberWithBsearch

findNumberWithBsearch.php

<?php
function bsearch($number, $arr, $low, $high) {
  //Traditional Recursive
  if ($low > $high) {
      return -1;
  }

  $mid = floor(($low + $high)/2);

  if ($arr[$mid] == $number) {
    return $mid; //Returns the index, Could also just return true if you just want the number to be found
  } elseif ($arr[$mid] > $number) {
      return bsearch($number, $arr, $low, $mid - 1);
  } elseif ($arr[$mid] < $number) {
      return bsearch($number, $arr, $mid + 1, $high);
  }
}

function findIndexOfLargestNumber($arr,$low,$high) {
  //we need 500 before we can proceed with the normal binary search
  if ($low == $high && $high == 0) return 0;
  while($low < $high) {
    $mid = $low + floor(($high - $low)/2);
    if($mid==0 || ($mid == $high) || ($arr[$mid]>$arr[$mid+1])) return $mid;
    else if($arr[$mid]>$arr[$low]) $low=$mid;
    else $high = $mid;
  }
}



$arr = array(8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1);
$number = 20;

$count = count($arr)-1;
$indexOfLargestNumber = findIndexOfLargestNumber($arr,0,$count); //Thinks it gonna be OnLogn
echo "Largest number index is $indexOfLargestNumber <br/>";

if ($number <= $arr[$indexOfLargestNumber]) echo "Index of the number $number (-1 indicates not found) => " . bsearch($number,$arr,0,$indexOfLargestNumber);
else echo "Result (-1 indicates not found) => " . bsearch($number,$arr,$indexOfLargestNumber+1,$count);
?>