V tomto článku budeme diskutovať o binárnom vyhľadávacom algoritme. Vyhľadávanie je proces hľadania určitého prvku v zozname. Ak sa prvok nachádza v zozname, proces sa nazýva úspešný a proces vráti umiestnenie tohto prvku. V opačnom prípade sa vyhľadávanie nazýva neúspešné.
Lineárne vyhľadávanie a binárne vyhľadávanie sú dve populárne techniky vyhľadávania. Tu budeme diskutovať o binárnom vyhľadávacom algoritme.
Binárne vyhľadávanie je technika vyhľadávania, ktorá efektívne funguje na triedených zoznamoch. Preto, aby sme hľadali prvok v nejakom zozname pomocou techniky binárneho vyhľadávania, musíme zabezpečiť, aby bol zoznam zoradený.
Binárne vyhľadávanie sa riadi prístupom rozdeľuj a panuj, v ktorom je zoznam rozdelený na dve polovice a položka sa porovnáva so stredným prvkom zoznamu. Ak sa potom nájde zhoda, vráti sa umiestnenie stredného prvku. V opačnom prípade hľadáme obe polovice v závislosti od výsledku dosiahnutého počas zápasu.
POZNÁMKA: Binárne vyhľadávanie môže byť implementované na triedených prvkoch poľa. Ak prvky zoznamu nie sú usporiadané zoradené, musíme ich najprv zoradiť.
Teraz sa pozrime na algoritmus binárneho vyhľadávania.
Algoritmus
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
Fungovanie binárneho vyhľadávania
Teraz sa pozrime na fungovanie Binárneho vyhľadávacieho algoritmu.
Aby sme pochopili fungovanie binárneho vyhľadávacieho algoritmu, zoberme si triedené pole. Na príklade bude ľahké pochopiť fungovanie binárneho vyhľadávania.
Existujú dva spôsoby implementácie binárneho vyhľadávacieho algoritmu -
- Iteratívna metóda
- Rekurzívna metóda
Rekurzívna metóda binárneho vyhľadávania sleduje prístup rozdeľuj a panuj.
Nech sú prvky poľa -
Nechajte prvok na vyhľadávanie, K = 56
Na výpočet musíme použiť nasledujúci vzorec stred z poľa -
mid = (beg + end)/2
Takže v danom poli -
prosiť = 0
koniec = 8
stred = (0 + 8)/2 = 4. Čiže 4 je stred poľa.
Teraz je nájdený prvok na vyhľadávanie. Algoritmus teda vráti index zhodného prvku.
Zložitosť binárneho vyhľadávania
Teraz sa pozrime na časovú zložitosť binárneho vyhľadávania v najlepšom prípade, priemernom prípade a najhoršom prípade. Uvidíme aj priestorovú zložitosť Binárneho vyhľadávania.
1. Časová zložitosť
| Prípad | Časová zložitosť |
|---|---|
| Najlepší prípad | O(1) |
| Priemerný prípad | O(logn) |
| V najhoršom prípade | O(logn) |
2. Zložitosť priestoru
| Priestorová zložitosť | O(1) |
- Priestorová zložitosť binárneho vyhľadávania je O(1).
Implementácia binárneho vyhľadávania
Teraz sa pozrime na programy binárneho vyhľadávania v rôznych programovacích jazykoch.
Program: Napíšte program na implementáciu binárneho vyhľadávania v jazyku 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)> Výkon
java programy
Tak, to je o článku všetko. Dúfam, že článok bude pre vás užitočný a poučný.