算法-搜索

发表于 分类于 阅读次数：
二分搜索

如果数组中的项按顺序排列，就可以不必进行线性搜索，而可以使用二分搜索。
查找时，先从中间数据开始，检查中间的项是否比我们要寻找的项大或小，并决定保留哪一半，并继续重复前面的搜索，直到找到需要搜索的值。
搜索长度呈指数递减，所以，最坏和平均时间复杂度为$O(logn)$，空间复杂度为$O(1)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function binSearch($arr, $search) {
    // 搜索数组的最大和最小下标
    $height = count($arr) - 1;
    $low = 0;
    while($low <= $height) {
        $mid = floor(($low + $height) / 2);
        if($arr[$mid] == $search) {
            return $mid;
        } elseif ($arr[$mid] < $search) {
            $low = $mid + 1;
        } elseif($arr[$mid] > $search) {
            $height = $mid -1;
        }
    }
    return '查找失败';
}

递归版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function binarySearchRecursion(array $arr, int $needle, int $low, int $high)
{
    if ($high < $low) return false;

    $middle = (int)(($high + $low) / 2);

    if ($arr[$middle] < $needle) {
        return binarySearchRecursion($arr, $needle, $middle + 1, $high);
    } elseif ($arr[$middle] > $needle) {
        return binarySearchRecursion($arr, $needle, $low, $middle - 1);
    } else {
        return true;
    }
}
重复二分搜索

假设我们有一个含有重复数据的数组，如果我们想从数组中找到某个数的第一次出现的位置，就可以修改上面的二分搜索。
需要修改的地方是找到搜索值时，将下标赋值给firstIndex，并不返回，并重复查找，直到$low > $high。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public function repetitiveBinarySearch($arr, $search)
{
    $low = 0;
    $high = count($arr);
    $firstIndex = -1;

    while ($low <= $high) {
        // 右移一位，即是：除二取整
        $middle = ($low + $high) >> 1;

        if ($arr[$middle] === $search) {
            $firstIndex = $middle;
            $high = $middle - 1;
        } elseif ($arr[$middle] > $search) {
            $high = $middle - 1;
        } else {
            $low = $middle + 1;
        }
    }

    return $firstIndex;
}
插值搜索

如果一个数组是均匀分布的，并且我们正在寻找的数据可能接近数组的末尾，那么从中间搜索可能不是一个好选择。 在这种情况下，插值搜索可能非常有用。插值搜索是对二分搜索算法的改进，插值搜索可以基于搜索的值选择到达不同的位置。例如，如果我们正在搜索靠近数组开头的值，它将直接定位到到数组的第一部分而不是中间。使用公式计算位置，如下所示：

$middle = low + [(key - arr[low]) * (high - low) / (arr[high] - arr[low])]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public function interpolationSearch($arr, $search)
{
    $low = 0;
    $high = count($arr) - 1;

    while ($arr[$low] != $arr[$high] && $search >= $arr[$low] && $search <= $arr[$high]) {
        $middle = intval($low + ($search - $arr[$low]) * ($high - $low) / ($arr[$high] - $arr[$low]));

        if ($arr[$middle] < $search) {
            $low = $middle + 1;
        } elseif ($arr[$middle] > $search) {
            $high = $middle - 1;
        } else {
            return $middle;
        }
    }

    if ($search == $arr[$low]) {
        return $low;
    }

    return -1;
}
指数搜索

在二分搜索中，我们在整个列表中搜索给定的数据。指数搜索通过决定搜索的下界和上界来改进二分搜索，这样我们就不会搜索整个列表。

  1. 我们通过查找第一个指数k来确定边界大小，其中值2^k的值大于搜索项。 现在，$2^k$和$2^{(k-1)}$分别成为上限和下限。
  2. 使用以上的边界来进行二分搜索。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    function exponentialSearch($arr, $search) {
        $length = count($arr);
        if ($length == 0) return -1;

        $bound = 1;

        while ($bound < $length && $arr[$bound] < $search) {
            $bound *= 2;
        }

        return binarySearchRecursion($arr, $search, $bound >> 1, min($bound, $length));
    }