1 <?php 2 /** 3 sequence search 4 从第一个元素开始，依次同每个元素比较 5 */ 6 function seq_search($arr,$n,$k){ 7 for($i=0;$i<$n;$i++){ 8 if($arr[$i]==$k){ 9 break; 10 } 11 } 12 if($i<$n){ 13 return $i; 14 }else{ 15 return -1; 16 } 17 } 18 19 /** 20 binary search 使用了递归 21 */ 22 function binary_search_recursive($arr,$low,$high,$k){ 23 if($low<=$high){ 24 $mid=intval(($low+$high)/2); 25 if($arr[$mid]==$k){ 26 return $mid; 27 }else if($arr[$mid]<$k){ 28 return binary_search($arr,$mid+1,$high,$k); 29 }else{ 30 return binary_search($arr,$low,$mid-1,$k); 31 } 32 } 33 return -1; 34 } 35 36 /** 37 binary search 未使用递归 38 */ 39 function binary_search($arr,$low,$high,$val){ 40 $mid = floor(($low+$high)/2); 41 while($val!=$arr[$mid]&&$low<$high){ 42 if($val<$arr[$mid]){ 43 $high = $mid-1; 44 } 45 if($val>$arr[$mid]){ 46 $low = $mid+1; 47 } 48 $mid = floor(($low+$high)/2); 49 } 50 return $val==$arr[$mid]?$mid:-1; 51 } 52 53 $arr = array(9,6,10,2,5,3,1,8); 54 echo seq_search($arr,8,2); 55 echo '<br/>'; 56 echo binary_search_recursive($arr,0,7,2); 57 echo '<br/>'; 58 echo binary_search($arr,0,7,2); 59