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