二分查找

二分查找

原理实现：有序集合从中间分为前后2部分，当要查当数值等于中间值，直接返回；当要查询数值大于中间值，则说明要查询的数值在后半部分，那么继续二分后半部分；当要查询数值小于中间数值时，说明要查询的数值在前半部分，那么继续二分前半部分。（过滤掉一半数据查询）

<?php
    /**
     * 递归实现
     * array $arr 有序数组
     * int $search 要查询的数字
     * int firstIndex 数组起始位置
     * int lastIndex 数组结束位置
     * @return 
     */
    function binarySearchRecursion(array $arr, $search, $lastIndex, $firstIndex = 0)
    {
        $len = count($arr);
        if ($len <= 0) {
            return -1;
        }
        $middle = intval(($firstIndex + $lastIndex) / 2);
        if ($search == $arr[$middle]) {//找到直接返回
            return $arr[$middle];
        } elseif ($search > $arr[$middle]) {//去后面查，数组起始位置变为$middle + 1。
            return binarySearchRecursion($arr, $search, $middle + 1, $lastIndex);
        } else {//去前面查，数组结束位置为$middle - 1。
            return binarySearchRecursion($arr, $search, $firstIndex, $middle - 1);
        }
        return -1;
    }

    /**
     * 递归实现
     * array $arr 有序数组
     * int $search 要查询的数字
     * @return 
     */
     function binarySearch($arr, $search)
     {
        $len = count($arr);
        if ($len <= 0 ) {
            return -1;
        }
        $firstIndex = 0;
        $lastIndex = $len - 1;
        while($firstIndex <= $lastIndex) {
            $middle = intval(($firstIndex + $lastIndex) / 2);
            if ($search == $arr[$middle]) {//出口
                return $arr[$middle];
            } elseif ($search > $arr[$middle]) {//去后面查，数组起始位置变为$middle + 1。
                $firstIndex = $middle + 1;
            } else {//去前面查，数组结束位置为$middle - 1。
                $lastIndex = $middle - 1;
            }
        }
        return -1;
     }

本作品采用《CC 协议》，转载必须注明作者和本文链接