二叉搜索
![二叉搜索](/img/Algorithm/feature-image---binary-search.webp)
二叉搜索是最流行、最高效的搜索算法。事实上,它是最快的搜索算法。和跳转排序一样,它也需要对数组进行排序。它是基于分而治之的方法,我们将数组分为两半,然后将我们要搜索的项目与中间的项目进行比较。如果中间的项目匹配,我们就返回中间元素的索引;否则,我们就根据项目的值移动到左右两半。
二叉搜索算法
假设我们有一个未排序的数组 A[]
,包含 n
个元素,我们想找到一个元素 X
。
-
设
lo
为0
,hi
为n - 1
。 -
当
lo
<hi
。- 设
mid
=lo + (hi - lo)/2
。 - 如果
A[mid]
==X
返回mid
。 - 如果
A[mid]
<X
,则lo
=mid+1
。 - else if
A[mid]
>X
thenhi
=mid-1
。
- 设
-
没有找到元素,所以返回
-1
。
二叉搜索示例
假设我们有一个数组。(1,2,3,4,5,6,7,8,9)
,我们想找到 X - 8
。
-
设
lo
为0
,hi
为8
。 -
计算
mid
为4
。由于A[mid]
<X
,设lo
=4+1
=5
。 -
计算
mid
为6
。由于A[mid]
<X
,设lo
=6+1
=7
。 -
计算 mid 为
7
。因为A[mid]
=8
,所以返回 7。
二叉搜索算法的实现
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int lo, int hi, int x) {
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
if (arr[m] == x) return m;
if (arr[m] < x)
lo = m + 1;
else
hi = m - 1;
}
return -1;
}
int main(void) {
int n = 9;
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int x = 8;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1) {
cout << "Element not found !!";
} else
cout << "Element found at index " << result;
return 0;
}
二叉搜索算法的复杂度
时间复杂度
- 平均情况
当我们进行二叉搜索时,我们搜索一半,丢弃另一半,每次都会将数组的大小减少一半。
时间复杂度的表达式是由递归给出的。
T(n) = T(n/2) + k , k is a constant.
这个递归的结果给出了 logn
,时间复杂度为 O(logn)
。它比线性搜索和跳转搜索都要快。
- 最佳情况
最好的情况是当中间元素是我们正在搜索的元素,并且在第一次迭代中被返回。最佳情况下的时间复杂度是 O(1)
。
- 最坏的情况
最坏情况下的时间复杂度与平均情况下的时间复杂度相同。最坏情况下的时间复杂度是 O(logn)
。
空间复杂度
在迭代执行的情况下,该算法的空间复杂度为 O(1)
,因为除了临时变量外,它不需要任何数据结构。
在递归实现的情况下,由于递归调用堆栈所需的空间,空间复杂度为 O(logn)
。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn