定义

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。在一个有序二维数组中，查找指定的值对应的键（下标）。

适用场景

有序数组

实现代码

<?php 
    public function binarySearch($arr=[], $key=null) {
        $left = 0;
        $right = count($arr) - 1;
        while( $left<=$right ) {
            $middle = floor( ($left+$right)/2 );
            if($key == $arr[$middle]) return $middle;
            elseif($key > $arr[$middle]) $left = $middle + 1;
            else  $right = $middle - 1;
        }
        return -1;
    }
?>

二分法变种

有时候数组虽然是有序的，但是可能有多个重复的值，这时我们的需求就要变动了，算法也要做相应的调整。

• 有重复值时查找第一个值对应的键（下标）
• 有重复值时查找最后一个值对应的键（下标）