Find which two values of an array a given value is between

Question

Suppose I have an array similar to this (actual values probably will not be so predictable):

$ar[0] = 5;
$ar[1] = 10;
$ar[2] = 15;
$ar[3] = 20;

and I have $n = 8, what would be a good way to find that $n falls between $ar[0] and $ar[1]? Preferably, the solution would avoid looping through the entire array, as this will probably repeated many times over on an array of varying size.

Edit:
Yes, the array will always be sorted.

Answer 1

For smaller arrays...

If your array is always sorted with smaller values at the bottom, you can cycle through until you get to one that is greater than your comparable number. When you reach that point, record the key, or the number of iterations it took to get there.

Answer 2

If you don't want to loop through the entire array, and your array is sorted, you can start in the middle, compare the value you are looking for, and based on the result select the first half or the second half of the array to continue with.

Answer 3

PHP has an array_search function built into the framework, but it natively doesn't use a binary search. Complements of the PHP array_search entry:

<?php
    function array_bsearch( $needle, $haystack, $comparator ) {
        $high = Count( $haystack ) -1;
        $low = 0;

        while ( $high >= $low ){
            $probe = Floor( ( $high + $low ) / 2 );
            $comparison = $comparator( $haystack[$probe], $needle );
            if ( $comparison < 0 ) {
                $low = $probe +1;
            } elseif ( $comparison > 0 ) {
                $high = $probe -1;
            } else {
                return $probe;
            }
        }

      // ---The loop ended without a match
      return -1;
    }
?>

Answer 4

Wtfuck, it's really easiest task.

<?php
$minDiff = end($array);
$takeLesser = true;
if ($inputValue > $minDiff) {
  $itemKey = key($array);
} else { 
  foreach ($array as $key => $value) {
    $diff = abs($value - $inputValue);
    if ($minDiff < $diff) {
      break;
    }
    if ($minDiff == $diff && $takeLesser) {
      continue;
    }
    $minDiff = $diff;
    $itemKey = $key;
  }
}  
$result = $array[$itemKey];