In diesem Artikel besprechen wir den binären Suchalgorithmus. Unter Suchen versteht man den Vorgang, ein bestimmtes Element in der Liste zu finden. Wenn das Element in der Liste vorhanden ist, wird der Prozess als erfolgreich bezeichnet und der Prozess gibt den Speicherort dieses Elements zurück. Andernfalls gilt die Suche als erfolglos.
Lineare Suche und binäre Suche sind die beiden beliebtesten Suchtechniken. Hier werden wir den binären Suchalgorithmus diskutieren.
Die binäre Suche ist die Suchtechnik, die bei sortierten Listen effizient funktioniert. Um ein Element in einer Liste mithilfe der binären Suchtechnik zu suchen, müssen wir daher sicherstellen, dass die Liste sortiert ist.
Die binäre Suche folgt dem Divide-and-Conquer-Ansatz, bei dem die Liste in zwei Hälften geteilt und das Element mit dem mittleren Element der Liste verglichen wird. Wenn die Übereinstimmung gefunden wird, wird die Position des mittleren Elements zurückgegeben. Andernfalls suchen wir in einer der beiden Hälften, abhängig vom Ergebnis, das durch das Spiel erzielt wird.
HINWEIS: Die binäre Suche kann für sortierte Array-Elemente implementiert werden. Wenn die Listenelemente nicht sortiert angeordnet sind, müssen wir sie zunächst sortieren.
Sehen wir uns nun den Algorithmus der binären Suche an.
Algorithmus
Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search Step 1: set beg = lower_bound, end = upper_bound, pos = - 1 Step 2: repeat steps 3 and 4 while beg val set end = mid - 1 else set beg = mid + 1 [end of if] [end of loop] Step 5: if pos = -1 print 'value is not present in the array' [end of if] Step 6: exit
Funktionsweise der binären Suche
Sehen wir uns nun die Funktionsweise des binären Suchalgorithmus an.
Um die Funktionsweise des binären Suchalgorithmus zu verstehen, nehmen wir ein sortiertes Array. Anhand eines Beispiels lässt sich die Funktionsweise der binären Suche leicht verstehen.
Was ist ein Java-Stack?
Es gibt zwei Methoden zum Implementieren des binären Suchalgorithmus:
Schnittstelle in Java
- Iterative Methode
- Rekursive Methode
Die rekursive Methode der binären Suche folgt dem Divide-and-Conquer-Ansatz.
Die Elemente des Arrays seien -
Das zu suchende Element sei: K = 56
Zur Berechnung müssen wir die folgende Formel verwenden Mitte des Arrays -
mid = (beg + end)/2
Also, im gegebenen Array -
bitten = 0
Ende = 8
Mitte = (0 + 8)/2 = 4. 4 ist also die Mitte des Arrays.
Jetzt ist das zu suchende Element gefunden. Der Algorithmus gibt also den Index des übereinstimmenden Elements zurück.
Komplexität der binären Suche
Sehen wir uns nun die zeitliche Komplexität der binären Suche im besten, durchschnittlichen und schlechtesten Fall an. Wir werden auch die räumliche Komplexität der binären Suche sehen.
string.substring Java
1. Zeitkomplexität
| Fall | Zeitkomplexität |
|---|---|
| I'm besten fall | O(1) |
| Durchschnittlicher Fall | O(logn) |
| Schlimmsten Fall | O(logn) |
2. Raumkomplexität
| Weltraumkomplexität | O(1) |
- Die räumliche Komplexität der binären Suche beträgt O(1).
Implementierung der binären Suche
Sehen wir uns nun die Programme der binären Suche in verschiedenen Programmiersprachen an.
Programm: Schreiben Sie ein Programm zur Implementierung der binären Suche in der Sprache C.
#include int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{11," 14, 25, 30, 40, 41, 52, 57, 70}; given array val="40;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result printf('the elements are - '); for (int i="0;" < n; i++) printf('%d ', a[i]); printf('
element %d', (res="=" -1) not present array'); at %d position array', res); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-5.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C++.</p> <pre> #include using namespace std; int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{10," 12, 24, 29, 39, 40, 51, 56, 70}; given array val="51;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result cout<<'the elements are - '; for (int i="0;" < n; i++) cout< <a[i]<<' cout<<'
element '<<val; (res="=" -1) not present array'; at '<<res<<' position 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-6.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C#.</p> <pre> using System; class BinarySearch { static int binarySearch(int[] a, int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; static void main() int[] a="{9," 11, 23, 28, 38, 45, 50, 56, 70}; given array int val="70;" value n="a.Length;" size of res="binarySearch(a," 0, n-1, store result console.write('the elements are - '); for (int i="0;" < n; i++) console.write(a[i] + ' console.writeline(); console.writeline('element (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-7.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in Java.</p> <pre> class BinarySearch { static int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; public static void main(string args[]) int a[]="{8," 10, 22, 27, 37, 44, 49, 55, 69}; given array val="37;" value n="a.length;" size of res="binarySearch(a," 0, n-1, store result system.out.print('the elements are: '); for (int i="0;" < n; i++) system.out.print(a[i] + ' system.out.println(); system.out.println('element is: (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-8.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in PHP.</p> <pre> = $beg) { $mid = floor(($beg + $end)/2); if($a[$mid] == $val) { return $mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if($a[$mid] <$val) { return binarysearch($a, $mid+1, $end, $val); } * if the item to be searched is greater than middle, then it can only in right subarray else $beg, $mid-1, -1; $a="array(7," 9, 21, 26, 36, 43, 48, 54, 68); given array $val="68;" value $n="sizeof($a);" size of $res="binarySearch($a," 0, $n-1, store result echo 'the elements are: '; for ($i="0;" $i < $n; $i++) ' , $a[$i]; <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> </$val)></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-9.webp" alt="Binary Search Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></val)></pre></val)></pre></val)></pre></val)> Ausgabe
Das ist also alles über den Artikel. Ich hoffe, der Artikel ist hilfreich und informativ für Sie.