迹忆客 专注技术分享

二叉搜索是最流行、最高效的搜索算法。事实上，它是最快的搜索算法。和跳转排序一样，它也需要对数组进行排序。它是基于分而治之的方法，我们将数组分为两半，然后将我们要搜索的项目与中间的项目进行比较。如果中间的项目匹配，我们就返回中间元素的索引；否则，我们就根据项目的值移动到左右两半。

二叉搜索算法

假设我们有一个未排序的数组 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 then hi= mid-1。
• 没有找到元素，所以返回 -1。

二叉搜索示例

1. 设 lo 为 0，hi 为 8。
2. 计算 mid 为 4。由于 A[mid]<X，设 lo=4+1=5。
3. 计算 mid 为 6。由于 A[mid]<X，设 lo=6+1=7。
4. 计算 mid 为 7。因为 A[mid]=8，所以返回 7。

假设我们有一个数组。(1,2,3,4,5,6,7,8,9)，我们想找到 X - 8。

二叉搜索算法的实现

#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)。