二元搜尋法

二元搜尋法的觀念
1.資料已排序好
2.取排序好的中間位置的值，與想要找的值做比對
3.如果比對不成功，搜尋範圍就剩原來的一半，
4.一直重覆步驟2,3

  
  /**
   * 以shaker法進行排序，以便進行二元搜尋。
   */
  $length=rand(8,10);
  
  for($i=0;$i<$length;$i++)
   $a[]=rand(100,200);

  $left=0;
  $right=$length-1;
  while($left<$right){
   $shift=0;   
   for($i=$left;$i<$right;$i++){
    if($a[$i]>$a[$i+1]){
     $tmp=$a[$i];
     $a[$i]=$a[$i+1];
     $a[$i+1]=$tmp;
     $shift=$i;
    }
   }
   $right=$shift;
   
   for($i=$right;$i>$left;$i--){
    if($a[$i]<$a[$i-1]){
     $tmp=$a[$i];
     $a[$i]=$a[$i-1];
     $a[$i-1]=$tmp;
     $shift=$i;
    }
   }
   $left=$i;
  }

  foreach($a as $num)
   echo $num."
\n";
  
  
  /**
   * 設定要找尋的值
   */
  $search='192';
  
  
  /**
   * 二元搜尋法
   */
  $low=0;
  $high=$length-1;
  $flag=0;
    
  while($low<=$high){
   $mid=(int)(($low+$high)/2);
   if($search>$a[$mid]){
    $low=$mid+1;
   }elseif($search<$a[$mid]){
    $high=$mid-1;
   }else{
    $flag=1;
    break;
   }
  }   
    
  if($flag)
   echo '所要找的值的陣列表示法是:'."\$a[$mid]"."
\n";
  else
   echo '找不到!';