In diesem Artikel implementieren wir einen ternären Suchalgorithmus und vergleichen seine Leistung mit dem binären Suchalgorithmus.
Voraussetzung:
Binärer Suchalgorithmus – Iterative und rekursive Implementierung
Bei der ternären Suche teilen wir unser Array in drei Teile (indem Sie zwei Mitte nehmen) und verwerfen bei jeder Iteration zwei Drittel unseres Suchraums. Auf den ersten Blick scheint es, dass die ternäre Suche schneller sein könnte als die Binäres Suchen, da ihre Zeitkomplexität bei einer Eingabe enthalten ist n Artikel sollten sein O(log3n), was weniger als die Zeitkomplexität der Binäres Suchen ist O(log2n). Bevor wir diese Behauptung analysieren, werfen wir zunächst einen Blick auf die C-, Java- und Python-Implementierung.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <stdio.h> // Ternärer Suchalgorithmus zur Rückgabe der Position von // Ziel `x` in einem gegebenen Array `A` der Größe `n` int TernarySearch(int arr[], int n, int x) { int low = 0, high = n - 1; while (low <= high) { int left_mid = low + (high - low) / 3; int right_mid = high - (high - low) / 3; // int left_mid = (2*low + high)/3; // int right_mid = (low + 2*high)/3; if (arr[left_mid] == x) { return left_mid; } else if (arr[right_mid] == x) { return right_mid; } else if (arr[left_mid] > x) { high = left_mid - 1; } else if (arr[right_mid] < x) { low = right_mid + 1; } else { low = left_mid + 1, high = right_mid - 1; } } return -1; } int main(void) { int A[] = { 2, 5, 6, 8, 9, 10 }; int target = 6; int n = sizeof(A) / sizeof(A[0]); int index = TernarySearch(A, n, target); if (index != -1) { printf("Element found at index %d", index); } else { printf("Element not found in the array"); } return 0; } |
Ergebnis:
Element found at index 2
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Main { // Ternärer Suchalgorithmus zur Rückgabe der Position von // Ziel `x` in einem gegebenen Array `A` public static int ternarySearch(int[] A, int x) { int left = 0, right = A.length - 1; while (left <= right) { int leftMid = left + (right - left) / 3; int rightMid = right - (right - left) / 3; // int leftMid = (2*left + right) / 3; // int rightMid = (left + 2*right) / 3; if (A[leftMid] == x) { return leftMid; } else if (A[rightMid] == x) { return rightMid; } else if (A[leftMid] > x) { right = leftMid - 1; } else if (A[rightMid] < x) { left = rightMid + 1; } else { left = leftMid + 1; right = rightMid - 1; } } return -1; } public static void main(String[] args) { int[] A = { 2, 5, 6, 8, 9, 10 }; int key = 6; int index = ternarySearch(A, key); if (index != -1) { System.out.println("Element found at index " + index); } else { System.out.println("Element not found in the array"); } } } |
Ergebnis:
Element found at index 2
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
# Ternärer Suchalgorithmus zur Rückgabe der Position von # Ziel `x` in einer gegebenen Liste `A`. def ternarySearch(A, x): (left, right) = (0, len(A) - 1) while left <= right: leftMid = left + (right - left) // 3 rightMid = right - (right - left) // 3 # leftMid = (2*left + right) // 3 # rightMid = (left + 2*right) // 3 if A[leftMid] == x: return leftMid elif A[rightMid] == x: return rightMid elif A[leftMid] > x: right = leftMid - 1 elif A[rightMid] < x: left = rightMid + 1 else: left = leftMid + 1 right = rightMid - 1 return -1 if __name__ == '__main__': A = [2, 5, 6, 8, 9, 10] key = 6 index = ternarySearch(A, key) if index != -1: print(f'Element found at index {index}') else: print('Element found not in the list') |
Ergebnis:
Element found at index 2
Wie wir sehen können, führt die ternäre Suche bei jeder Iteration höchstens 4 Vergleiche durch, im Vergleich zur Binäres Suchen, die nur 2 Vergleiche durchführt. So,
Für die Binäres Suchen – T(n) = 2clog2n + O(1)
Für ternäre Suche – T(n) = 4clog3n + O(1)
Durch Anwendung einfacher Mathematik können wir feststellen, dass die Zeit, die eine ternäre Suche benötigt, gleich ist 2.log32 mal die benötigte Zeit binärer Suchalgorithmus.
Jetzt seit 2.log32 > 1, bekommen wir tatsächlich mehr Vergleiche mit der ternären Suche.
Daher ergibt eine ternäre Suche immer noch die gleiche asymptotische Komplexität O(log(n)) Suchzeit, erhöht aber die Komplexität der Implementierung. Dasselbe Argument gilt für eine quaternäre Suche oder eine k–näre Suche nach jeder anderen höheren Ordnung.
Wie von Oriba Desu in den Kommentaren unten hervorgehoben, können wir eine ternäre Suche verwenden, um das Extremum (Minimum oder Maximum) von an zu finden unimodale Funktion.