にぶんたんさく

gistfile1.php

<?php
/**                                                                                                                                                                    
 * 「ビューティフル・コード」（P.91）で、普通のプログラマは二分探索をまともに書けないと煽られたので書いた。                                                            
 */

function search($needle,$haystack)
{ 
  $start=0;
  $end=count($haystack);
  do
  { 
    $mid=floor($start+($end-$start)/2); //桁あふれ防止追加                                                                                             
    if($haystack[$mid]==$needle)
      return $mid;
    else if($haystack[$mid]<$needle)
      $start=$mid+1;
    else
      $end=$mid;
  }
  while($start!=$end);
  return -1;
}

function report($needle,$haystack) 
{ 
  foreach($haystack as $index=>$val)
    echo "[$index]:$val ";
  echo "\n";  
  echo "search: $needle\n";
  echo "result index: ".search($needle,$haystack)."\n";
}

$sortedArray=array(1,2,3,5,6,8);
report(1,$sortedArray);
report(8,$sortedArray);
report(5,$sortedArray);
report(10,$sortedArray);