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

Najboljša zapletenost -Pri binarnem iskanju se najboljši primer pojavi, ko je element za iskanje najden v prvi primerjavi, tj. ko je sam prvi srednji element element, ki ga je treba iskati. Najboljša časovna zapletenost binarnega iskanja je O(1). Povprečna zapletenost primera -Povprečna časovna zapletenost primera binarnega iskanja je O (prijava). Kompleksnost v najslabšem primeru -Pri binarnem iskanju pride do najslabšega primera, ko moramo ves čas zmanjševati iskalni prostor, dokler nima samo enega elementa. Najslabši primer časovne zapletenosti binarnega iskanja je O (prijava).

2. Kompleksnost prostora

• 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 &gt;= 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 &gt;= 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 &gt;= 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 &gt;= 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>&apos; , &apos;Element to be searched is: &apos; , $val; if ($res == -1) echo &apos; <br>&apos; , &apos;Element is not present in the array&apos;; else echo &apos; <br>&apos; , &apos;Element is present at &apos; , $res , &apos; position of array&apos;; ?&gt; </$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&apos;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.