非递归二分查找算法和利用二分查找算法求平方根

1.二分查找算法

function binarySearch(array $arr, int $n) {
    $low = 0;
    $high = count($arr) - 1;
    while($low <= $high) {
        $mid = intval(($low + $high) / 2);//$mid = $low + ($high - $low) / 2
        if($arr[$mid] < $n) {
            $low = $mid + 1;
        } elseif ($arr[$mid] > $n) {
            $high = $mid - 1;
        } else {
            return "$n in array, offset is $mid";//直接返回
        }
    }
    return "$n is not in array";
}

2.二分查找算法求平方根

function squareRoot(float $n) {
    if ($n < 0) {
        return ‘‘;
    } elseif ($n < 1) {
        $less = $n;
        $bigger = 1;
    } else {
        $less = 0;
        $bigger = $n;
    }
    $value = floatval(($less + $bigger) / 2);
    while(abs($value * $value - $n) > 0.000001) {//精度
        $value = ($less + $bigger) / 2;
        if($value * $value > $n) {
            $bigger = $value - 0.000001;
        } else if($value * $value < $n) {
            $less = $value + 0.000001;
        } else {
            return $value;
        }
    }
    return $value;
}

3.应用的局限性
（1）数据结构为数组，需要连续的内存空间，当数据量过大时，会出现无法分配内存的情况。
（2）数据有序。

非递归二分查找算法和利用二分查找算法求平方根

原文：https://www.cnblogs.com/tutuut/p/13296768.html