二分查找的递归与非递归实现

题目

二分查找的递归与非递归实现

思路

• mid=(min+max)/2; 等价于 min+(max-min)/2 ,这样写能防止min+max溢出;
• mid=(min+max)/2 = min=min+(max-min)>>1 （右移一位等于除以2）

代码实现

//非递归
function biSearch($arr, $num) {
    $min = 0;
    $max = count($arr) - 1;
    while($min <= $max) {
    	//等价于min+(max-min)/2,这样写能防止min+max溢出，写>为位运算min=min+(max-min)>>1的形式更高效 
        $mid = floor(($min + $max)/2);

        if ($num < $arr[$mid]) {
            $max = $mid - 1;
        } else if ($num > $arr[$mid]) {
            $min = $mid + 1;
        } else {
            return $mid;
        }
    }
    return false;//未找到 
}
//递归
function binaryRecursive(&$arr, $low, $top, $target) {
    if ($low <= $top) {
    	return false;
    }
    $mid = floor(($low+$top) / 2);
    if ($arr[$mid] == $target) {
        return $mid;
    } else if ($arr[$mid] < $target) {
        return binaryRecursive($arr, $mid+1, $top, $target);
    } else {
        return binaryRecursive($arr, $low, $mid-1, $target);
    }
}

$arr = [1,2,5,6,7,9];
echo biSearch($arr, 7);
echo "===================================";
echo binaryRecursive($arr, 0, sizeof($arr), 7);

结果

4===================================4