二分查找法|折半查找法

概念

- 二分法概念二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法

递归二分法

/**
 * 递归二分法|折半查找法
 *  必要的前提是：必须是一个有需的数组
 *
 * @param  array   $arr 区间
 * @param  string  $search 搜索
 * @param  int     $min 最小值
 * @param  int     $max 最大值
 *
 * @return string
 */
static function dichotomy(array $arr, string $search, int $min = 0, int $max = 0)
{
    $count = count($arr);
    if (!$count) return '';
    // 先设置最大与最小值
    // $min = 0;
    if ($max == 0){
        // 注意下标
        $max = $count - 1;
    }
    $middle = intval(($min + $max) / 2);

    if ($arr[$middle] == $search){ // 如果是中位数，那么返回结束
        return [
            'value' => $arr[$middle],
            'index' => $middle,
        ];
    }else if ($arr[$middle] > $search){ // 如果搜索值大于中位数，那么区间就在中位数与最大值之间
        if ($arr[$middle] == $max){ // 如果最大值还是上一轮的最大值，说明这个中间数在最小与最大值之间，且不存在此数组内
            return 'search：' . $search . '，在最小值[' . $min . ']与最大值[' . $max . ']之间，且不再当前数组内。';
        }
        $max = $arr[$middle];
    }else if ($arr[$middle] < $search){ // 小于中位数，那么区间就在最小值与中位数之间
        if ($arr[$middle] == $min){ // 如果最小值还是上一轮的最小值，说明这个中间数在最小与最大值之间，且不存在此数组内
            return 'search：' . $search . '，在最小值[' . $min . ']与最大值[' . $max . ']之间，且不再当前数组内。';
        }
        $min = $arr[$middle];
    }else{ // 如果刚好在两位数的中间
        return '';
    }
    return self::dichotomy($arr, $search, $min, $max);
}

循环二分法

/**
 * 二分查找的循环法
 *
 * @param  array   $arr
 * @param  string  $search
 *
 * @return array|string
 */
static function dichotomy_while(array $arr, string $search)
{

    $count = count($arr);
    if (!$count) return '';
    $min = 0;
    // 注意下标
    $max = $count - 1;
    // 返回值
    $return = '';

    // 循环法
    $break = false;
    while (!$break){
        $middle = intval(($min + $max) / 2);
        if ($arr[$middle] == $search){
            $return = [
                'value' => $arr[$middle],
                'index' => $middle,
            ];
            $break = true;
        }else if ($arr[$middle] > $search){
            if ($arr[$middle] == $max){ // 如果最大值还是上一轮的最大值，说明这个中间数在最小与最大值之间，且不存在此数组内
                $return = 'search：' . $search . '，在最小值[' . $min . ']与最大值[' . $max . ']之间，且不再当前数组内。';
                $break = true;
            }
            $max = $arr[$middle];
        }else if ($arr[$middle] < $search){
            if ($arr[$middle] == $min){ // 如果最小值还是上一轮的最小值，说明这个中间数在最小与最大值之间，且不存在此数组内
                $return = 'search：' . $search . '，在最小值[' . $min . ']与最大值[' . $max . ']之间，且不再当前数组内。';
                $break = true;
            }
            $min = $arr[$middle];
        }else{
            $break = true;
        }
    }
    return $return;
}