Thursday, March 27, 2014

Binary chop in PHP

<?php

/* PHP is pass by value for function arguments
 * http://www.php.net/call_user_func has the mechanism
 * inbuilt to make calls to different bchop implementations.
 * Using call_user_func is left as an exercise for whosoever
 * reads and wants to do it.
 */
    function bchop (array $arr, $n, $key)
    {
      $min = 0;
      $max = $n;
      while ($min < $max) {
        $middle = $min + (($max - $min) >> 1);
        if ($key > $arr [$middle])
          $min = $middle + 1;
        else
          $max = $middle;
      }
      if ($arr[$min] == $key) return $min;
      else
        return -1;
    }

    $a = array(3, 4, 5, 10, 20, 21, 25, 29, 31, 35);
    $idx = bchop($a, sizeof($a), 20);

    print $idx;
?>

No comments:

Post a Comment