/**
 * 二分查找（Binary Search）算法，也叫折半查找算法。二分查找的思想非常简单，有点类似分治的思想。
 * 二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，
 * 将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
 *
 * 循环写法
 * @param array $array      待查找的数组
 * @param int $findVal      要查找的值
 * @return int              返回找到的数组键
 */
function binarySearch($array, $findVal)
{
    // 非数组或者数组为空，直接返回-1
    if (!is_array($array) || empty($array)) {
        return -1;
    }
    // 查找区间，起点和终点
    $start = 0;
    $end = count($array) - 1;
    while ($start <= $end) {
        // 以中间点作为参照点比较，取整数
        $middle = intval(($start + $end) / 2);
 
        if ($array[$middle] > $findVal) {
            // 查找数比参照点小，则要查找的数在左半边
            // 因为 $middle 已经比较过了，这里需要减1
            $end = $middle - 1;
 
        } elseif ($array[$middle] < $findVal) {
            // 查找数比参照点大，则要查找的数在右半边
            // 因为 $middle 已经比较过了，这里需要加1
            $start = $middle + 1;
 
        } else {
            // 查找数与参照点相等，则找到返回
            return $middle;
        }
    }
    // 未找到，返回-1
    return -1;
}
 
// 调用
$array = [10,12,16,19,20,34,56,78,84,95,100];
echo binarySearch($array, 84);

/**
 * 递归写法
 * @param array $array  待查找的数组
 * @param int $findVal  要查找的值
 * @param int $start    查找区间，起点
 * @param int $end      查找区间，终点
 * @return int          返回找到的数组键
 */
function binarySearch($array, $findVal, $start, $end)
{
    // 以中间点作为参照点比较，取整数
    $middle = intval(($start + $end) / 2);
    if ($start > $end) {
        return -1;
    }
    if ($findVal > $array[$middle]) {
        // 查找数比参照点大，则要查找的数在右半边
        return binarySearch($array, $findVal, $middle + 1, $end);
 
    } elseif ($findVal < $array[$middle]) {
        // 查找数比参照点小，则要查找的数在左半边
        return binarySearch($array, $findVal, $start, $middle - 1);
 
    } else {
        return $middle;
    }
}
 
// 调用
$array = [10,12,16,19,20,34,56,78,84,95,100];
echo binarySearch($array, 95, 0, count($array)-1);