二分查找隐藏的那个bug

看一段二分查找代码

function binarySearch($arr,$target){
    $low = 0;
    $hight = count($arr)-1;
    while($low <=$hight){
        $mid = ($low+$hight) /2;
        if($target == $arr[$mid]){
            return $mid;
        }elseif ($target < $arr[$mid]){ //左边找
            $hight = $mid - 1;
        }else{  //右边找
            $low = $mid + 1;
        }
    }
    return -1;
}

递归实现

function binarysearch2($arr,$low,$hight,$target){
    if($low <=$hight){
        $mid = ($low + $hight) / 2;
        if($target == $arr[$mid]){ 
            echo $mid;
        }elseif($target < $arr[$mid]){  //左边找
            binarysearch2($arr,$low,$mid-1,$target);
        }else{   //右边找
            binarysearch2($arr,$mid+1,$hight,$target);
        }
    }else{
        echo -1;
    }
}

当low+high的值超过了最大的正int值 (231 - 1) 的时候, mid会变成负值, 这个时候会抛出异常
正确的方法是：
将 low+mid = hight-$low) /2;

若查找元素在数组中重复出现的话,可以修改一下代码
支持php5.4以上版本

function binarySearch3($arr,$target){
    $indexArr = array();
    $low = 0;
    $hight = count($arr)-1;
    while($low <=$hight){
        // $mid = ($low+$hight) /2;
        $mid = $low+($hight-$low) /2;
        if($target == $arr[$mid]){      //找到第一个相同元素
            $mid = $mid -1;             //左边找相同元素
            while($mid >= $low && $arr[$mid] == $target){  
                $indexArr[] = $mid;
                $mid--;
            }
            $mid = $mid +1;             //右边找相同元素
            while($mid <= $hight && $arr[$mid] == $target){
                $indexArr[] = $mid;
                $mid++;
            }
            return $indexArr;
        }elseif ($target < $arr[$mid]){ //左边找
            $hight = $mid - 1;
        }else{  //右边找
            $low = $mid + 1;
        }
    }
    return -1;
}