二分搜索
如果数组中的项按顺序排列,就可以不必进行线性搜索,而可以使用二分搜索。
查找时,先从中间数据开始,检查中间的项是否比我们要寻找的项大或小,并决定保留哪一半,并继续重复前面的搜索,直到找到需要搜索的值。
搜索长度呈指数递减,所以,最坏和平均时间复杂度为$O(logn)$,空间复杂度为$O(1)$。
1 | function binSearch($arr, $search) { |
递归版本:
1 | function binarySearchRecursion(array $arr, int $needle, int $low, int $high) |
重复二分搜索
假设我们有一个含有重复数据的数组,如果我们想从数组中找到某个数的第一次出现的位置,就可以修改上面的二分搜索。
需要修改的地方是找到搜索值时,将下标赋值给firstIndex
,并不返回,并重复查找,直到$low > $high
。
1 | public function repetitiveBinarySearch($arr, $search) |
插值搜索
如果一个数组是均匀分布的,并且我们正在寻找的数据可能接近数组的末尾,那么从中间搜索可能不是一个好选择。 在这种情况下,插值搜索可能非常有用。插值搜索是对二分搜索算法的改进,插值搜索可以基于搜索的值选择到达不同的位置。例如,如果我们正在搜索靠近数组开头的值,它将直接定位到到数组的第一部分而不是中间。使用公式计算位置,如下所示:
$middle = low + [(key - arr[low]) * (high - low) / (arr[high] - arr[low])]$
1 | public function interpolationSearch($arr, $search) |
指数搜索
在二分搜索中,我们在整个列表中搜索给定的数据。指数搜索通过决定搜索的下界和上界来改进二分搜索,这样我们就不会搜索整个列表。
- 我们通过查找第一个指数k来确定边界大小,其中值2^k的值大于搜索项。 现在,$2^k$和$2^{(k-1)}$分别成为上限和下限。
- 使用以上的边界来进行二分搜索。
1
2
3
4
5
6
7
8
9
10
11
12function 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));
}