学步园

刚才将排序和查找算法放在一起，感觉不方便阅读，因此将查找算法拿出来，供大家讨论

php基于快速排序实现二分查找

/**
 * Description:php实现二分查找算法的类
 * @author wzy
 */
class binary_search{
	public $arr;
	public $key;
	
	function __construct($arr,$key){
		//这里初始化的数组已经是有序数组
		$this->arr=$arr;
		$this->key=$key;
	}
	
	function binarysearch(){
		$start=0;
		$end=count($this->arr)-1;
		
		while($start<=$end){
			//mid的取值可以为上整数或者下整数
			$mid=ceil(($start+$end)/2);
			//$mid=($start+$end)>>1;
			//$mid=intval(($start+$end)/2);
			if($this->arr[$mid]<$this->key){
				$start=$mid+1;
			}else if($this->arr[$mid]>$this->key){
				$end=$mid-1;
			}else{
				return $mid;
			}
		}
	}
}

可能大家还会遇到这种情况，数组中的元素有重复数据，需要返回的是重复数据中的第一个元素的位置，例如

$arr=array(1,2,3,4,5,6,6,6,6,7,8);查找6这个元素时返回的位置应该为5,而不是其他（下标从0开始计数），这样需要在返回的mid进行判断，代码如下：

/**
 * Description:php实现二分查找算法的类
 * @author wzy
 */
class binary_search{
	public $arr;
	public $key;
	
	function __construct($arr,$key){
		//这里初始化的数组已经是有序数组
		$this->arr=$arr;
		$this->key=$key;
	}
	
	function binarysearch(){
		$start=0;
		$end=count($this->arr)-1;
		
		while($start<=$end){
			//mid的取值可以为上整数或者下整数
			$mid=ceil(($start+$end)/2);
			//$mid=($start+$end)>>1;
			//$mid=intval(($start+$end)/2);
			if($this->arr[$mid]<$this->key){
				$start=$mid+1;
			}else if($this->arr[$mid]>$this->key){
				$end=$mid-1;
			}else{
				//返回第一个匹配的元素
				for($i=$mid-1;$i>=0;$i--){
					if($this->arr[$i]==$this->key){
						$mid=$i;
					}else{
						break;
					}
				}
				return $mid;
			}
		}
	}
}