二分查找的前提是待查找的数组是有序的,其基本思想是分而治之,折半减少查找范围。

function binary_search( $arr, $num )
{
	$left = $right = array();
    $begin = current(array_keys($arr));
    $end = end(array_keys($arr));
    $mid = intval(($begin + $end)/2);    
    
    for($i = $begin; $i < $mid; $i++)
        $left[$i] = $arr[$i];
    for( $i = $mid +1; $i <= $end; $i++)
        $right[$i] = $arr[$i];
    
    if( $num == $arr[$mid] )
        return $mid;
    if( $num < $arr[$mid] )
        return binary_search($left,$num);
    if( $num > $arr[$mid] )
        return binary_search($right,$num);
}

function binary_search1(&$arr, $low, $top, $target)
{
	if( $target < $arr[$low] || $target > $arr[$top])
		return -1;
	if( $low < $top ){
		$mid = intval(($low + $top)/2);
		if( $num == $arr[$mid] ){
	        return $mid;
		}elseif( $num < $arr[$mid] ){
	        return binary_search1($arr, $low, $mid-1, $target);
		}else{
	        return binary_search1($arr, $mid+1, $top, $target);
		}
	}else{
		return -1;
	}	
}

上面的binary_search()是最原始的版本,随手写的,只是实现的功能,但是没有效率。binary_search1()直接针对索引进行查找,相比上一版本效率更高。

稍作修改,二分查找可以有递归实现(上面的实现方法)和非递归实现。

function binary_search2(&$arr, $low, $top, $target)
{
	while( $low <= $top ){
		$mid = intval(($low+$top)/2);
		if( $target == $arr[$mid])
			return $mid;
		elseif ( $target < $arr[$mid] ) {
			$top = $mid - 1;
		}else{
			$low = $mid + 1;
		}
	}
	return -1;
}