PHP 二分查找算法的实现

by kingzcheung on October 14, 2016

二分查找算法查找数组中的某个值,前提是这个数组已经排好了序.

大体步骤如下:

  • 先取数组中间的值floor((low+top)/2)
  • 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作;若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作
  • 重复第二步操作直至找出目标数字

这里有两种方式可以实现,循环法和递归法:

<?php

/// 先取数组中间的值floor((low+top)/2),
/// 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作;若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作
/// 重复第二步操作直至找出目标数字

namespace Search;

/**
 * 二分查找算法
 * Class Binary
 * @package Search
 */
class Binary {

    /**
     * 循环查找
     * @param array $arr    要查找的数组
     * @param int $begin    查找起点
     * @param int $end      查找终点
     * @param int $search   要查找的值
     * @return int          返回索引
     */

    public static function findOfLoop(array $arr, int $begin, int $end, int $search): int {
        while ($begin <= $end) {
            $mid = (int)floor(($begin + $end) / 2);
            if ($arr[$mid] == $search) {
                return $mid;
            } else if ($arr[$mid] < $search) {
                //如果这个数字在二分法的右半区
                $begin = $mid + 1;
            } else {
                //如果这个数据在二分法的左半区
                $end = $mid - 1;
            }
        }
        return -1;
    }

    /**
     * 递归方式查找
     * @param array $arr    要查找的数组
     * @param int $begin    查找起点
     * @param int $end      查找终点
     * @param int $search   要查找的值
     * @return int          返回索引
     */

    public static function findOfRecursive(array $arr, int $begin, int $end, int $search): int {
        if ($begin <= $end) {
            $mid = (int)floor(($begin + $end) / 2);
            if ($arr[$mid] == $search) {
                return $mid;
            } else if ($arr[$mid] < $search) {
                return self::findOfRecursive($arr, $mid + 1, $end, $search);
            } else if ($arr[$mid] > $search) {
                return self::findOfRecursive($arr, 0, $mid - 1, $search);
            }
        }
        return -1;
    }

}