二分查找

非递归

		function binarySearch($arr,$key){
			$low=0;
			$high=count($arr)-1;
			while($low<=$high){
				$mid=floor(($low+$high)/2);
				if($arr[$mid]==$key){
					return $mid;
				}
				if($arr[$mid]>$key){
					$high=$mid-1;
				}
				if($arr[$mid]<$key){
					$low=$mid+1;
			}

		}
		return -1;
	}
		$array=array(1,5,6,7,8,33,44,66);
		echo binarySearch($array,44);

递归

			function binarySearch($arr,$low,$high,$key){
				if($low<=$high){
					$mid=floor(($low+$high)/2);
					if($key==$mid){
						return $mid;
				}
					if($key<$mid){
						return binarySearch($arr,$low,$mid-1,$key);
				}
					if($key>$mid){
						return binarySearch($arr,$mid+1,$high,$key);
				}
			}
			return -1;
		}
		$array=array(1,5,6,7,8,33,44,66);
		echo binarySearch($array,0,7,44);

	测试运行结果：6

###算法要求：

1.必须采用顺序存储结构

2.必须按关键字大小有序排列。

###算法复杂度

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.时间复杂度无非就是while循环的次数！ 所以时间复杂度可以表示O()=O(logn)