V tem članku bomo razpravljali o algoritmu binarnega iskanja. Iskanje je postopek iskanja določenega elementa na seznamu. Če je element prisoten na seznamu, se postopek imenuje uspešen in proces vrne lokacijo tega elementa. V nasprotnem primeru se iskanje označi za neuspešno.
Linearno iskanje in binarno iskanje sta dve priljubljeni tehniki iskanja. Tukaj bomo razpravljali o algoritmu binarnega iskanja.
Binarno iskanje je tehnika iskanja, ki učinkovito deluje na razvrščenih seznamih. Zato moramo za iskanje elementa na nekem seznamu s tehniko binarnega iskanja zagotoviti, da je seznam razvrščen.
Binarno iskanje sledi pristopu deli in vladaj, pri katerem je seznam razdeljen na dve polovici, element pa se primerja s srednjim elementom seznama. Če je ujemanje takrat najdeno, se vrne lokacija srednjega elementa. V nasprotnem primeru iščemo v katerem koli od polčasov, odvisno od rezultata, doseženega skozi tekmo.
OPOMBA: Binarno iskanje je mogoče izvesti na razvrščenih elementih polja. Če elementi seznama niso razvrščeni, jih moramo najprej razvrstiti.
Zdaj pa si oglejmo algoritem binarnega iskanja.
Algoritem
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
Delovanje binarnega iskanja
Zdaj pa poglejmo delovanje algoritma binarnega iskanja.
Da bi razumeli delovanje algoritma binarnega iskanja, vzemimo razvrščeno polje. S primerom bo enostavno razumeti delovanje binarnega iskanja.
Obstajata dve metodi za implementacijo algoritma binarnega iskanja -
- Iterativna metoda
- Rekurzivna metoda
Rekurzivna metoda binarnega iskanja sledi pristopu deli in vladaj.
Naj so elementi matrike -
Naj bo element za iskanje K = 56
Za izračun moramo uporabiti spodnjo formulo sredina niza -
mid = (beg + end)/2
Torej, v danem nizu -
beračiti = 0
konec = 8
sredina = (0 + 8)/2 = 4. Torej je 4 sredina polja.
Zdaj je element za iskanje najden. Tako bo algoritem vrnil indeks ujemajočega se elementa.
Kompleksnost binarnega iskanja
Zdaj pa poglejmo časovno kompleksnost binarnega iskanja v najboljšem, povprečnem in najslabšem primeru. Videli bomo tudi prostorsko kompleksnost binarnega iskanja.
1. Časovna zapletenost
| Ovitek | Časovna zapletenost |
|---|---|
| Najboljši primer | O(1) |
| Povprečen primer | O (prijava) |
| V najslabšem primeru | O (prijava) |
2. Kompleksnost prostora
| Kompleksnost prostora | O(1) |
- Prostorska kompleksnost binarnega iskanja je O(1).
Implementacija binarnega iskanja
Zdaj pa si oglejmo programe binarnega iskanja v različnih programskih jezikih.
Program: Napišite program za implementacijo binarnega iskanja v jeziku 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)> Izhod
Torej, to je vse o članku. Upam, da vam bo članek koristen in informativen.