php二分查找

算法思想:又叫折半查找,要求待查找的序列有序。每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程。直到查找到了为止,否则序列中没有待查的关键字。

优点: 优点是比较次数少,查找速度快,平均性能好;

缺点:要求待查表为有序表,且插入删除困难。

因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

二分查找下面实现2种方法:

递归:

public function searchNum( $a , $lo, $hi, $search ){
		
		$mid = intval(($lo+$hi)/2);
		if( $a[$mid] == $search ){
			return $mid;
		}else if( $a[$mid] < $search ){
			return $this->searchNum( $a, $mid+1,$hi ,$search );
		}else{
			return $this->searchNum( $a, $lo,$mid-1 ,$search );
		}
		
		
	}
	
	

while循环查找:

	public function searchNum1($a,$search){
		$low = 0;
		$hi = count($a)-1;
		while( $low <=  $hi ){
			$mid = intval(($low+$hi)/2);
			if( $a[$mid] == $search ){
				echo $mid;
				break;
			}else if( $a[$mid] < $search ){
				$low = $mid+1;
			}else{
				$hi = $mid-1;
			}
		}
	}

查询数组中第一次出现的位置:

public function  biSearch($array,$a){
		$low=0;
		$hi=count($array)-1;
		$mid=0;
		while($low<$hi){
			$mid=intval(($low+$hi)/2);
			if($array[$mid]<$a){
				$low=$mid+1;
			}else{
				$hi=$mid;
			}
		}
		if($array[$low]!=$a){
			return -1;
		}else{
			return $low;
		}
	}

查询数组最后出现的位置:

public function  biSearch2($array,$a){
		$low=0;
		$hi=count($array)-1;
		$mid=0;
		while($low<$hi){
			$mid=intval(($low+$hi+1)/2);
			if($array[$mid]<=$a){
				$low=$mid;
			}else{
				$hi=$mid-1;
			}
		}
		if($array[$low]!=$a){
			return -1;
		}else{
			return $low;
		}
	}

调用方式:

        $a = array(10,20,30);
		$search = 30;
		
		$this->searchNum1($a,$search);
	
		echo $this->searchNum( $a, 0, count( $a )-1 , 30);
		
		
		$array = array(10,20,30,40,40,100);
		echo $this->biSearch($array, 40);
		echo $this->biSearch2($array, 40);

输出结果:

2 2 3 4