二叉搜尋

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 二叉搜尋演算法
  2. 二叉搜尋示例
  3. 二叉搜尋演算法的實現
  4. 二叉搜尋演算法的複雜度
二叉搜尋

二叉搜尋是最流行、最高效的搜尋演算法。事實上,它是最快的搜尋演算法。和跳轉排序一樣,它也需要對陣列進行排序。它是基於分而治之的方法,我們將陣列分為兩半,然後將我們要搜尋的專案與中間的專案進行比較。如果中間的專案匹配,我們就返回中間元素的索引;否則,我們就根據專案的值移動到左右兩半。

二叉搜尋演算法

假設我們有一個未排序的陣列 A[],包含 n 個元素,我們想找到一個元素 X

  • lo0hin - 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,2,3,4,5,6,7,8,9),我們想找到 X - 8

  • lo0hi8
  • 計算 mid4。由於 A[mid]<X,設 lo=4+1=5
  • 計算 mid6。由於 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 avatar Harshit Jindal avatar

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

相關文章 - Search Algorithm