function twoSplitSearch($arr, $search){
    $result = false;
    $left = 0;
    $right = count($arr) - 1;
    while($left<=$right){
        $mid = (int)(($left + $right)/2);
        if($arr[$mid]<$search){
            $left = $mid + 1;
        } elseif ($arr[$mid]>$search){
            $right = $mid - 1;
        } else {
            $result = $mid;
            break;
        }
    }

    return $result;
}
$arr = [1,2,3,4,7,9];
echo twoSplitSearch($arr, 9);

时间复杂度计算：

假如数组有N个元素，

第一次查找有 N/2个元素，

第二次查找有 N/4 个元素，

即第K次查找有 N/2^K 个元素

最复杂的可能是查找到只剩下一个元素，

即 

N/2^K = 1

2^K = N

K = log2N

所以时间复杂度为 O(log2N) (2为底数)

来自ansion博客 

http://www.tp0.top

2018-03-05 22:36:45