logo

TechCodeview

Algoritem binarnega iskanja – iterativna in rekurzivna implementacija

Binarno iskanje Algoritem je iskalni algoritem uporabljeno v razvrščeni matriki po večkratno delitev iskalnega intervala na pol . Ideja binarnega iskanja je uporaba informacije, da je niz razvrščen, in zmanjšanje časovne kompleksnosti na O(log N).

Binarno iskanje je iskalni algoritem, ki se uporablja za iskanje položaja ciljne vrednosti znotraj a razvrščeno niz. Deluje tako, da večkrat razdeli iskalni interval na pol, dokler ni najdena ciljna vrednost ali pa je interval prazen. Interval iskanja se prepolovi s primerjavo ciljnega elementa s srednjo vrednostjo iskalnega prostora.

tretja normalna oblika

Če želite uporabiti algoritem binarnega iskanja:



  • Struktura podatkov mora biti razvrščena.
  • Dostop do katerega koli elementa podatkovne strukture zahteva konstanten čas.

Algoritem binarnega iskanja:

V tem algoritmu je

  • Iskalni prostor razdelite na dve polovici z iskanje srednjega indeksa mid .

Iskanje srednjega indeksa mid v algoritmu binarnega iskanja

  • Primerjajte srednji element iskalnega prostora s ključem.
  • Če je ključ najden na srednjem elementu, se postopek prekine.
  • Če ključa ni mogoče najti na srednjem elementu, izberite, katera polovica bo uporabljena kot naslednji iskalni prostor.
    • Če je ključ manjši od srednjega elementa, se za naslednje iskanje uporabi leva stran.
    • Če je ključ večji od srednjega elementa, se za naslednje iskanje uporabi desna stran.
  • Ta postopek se nadaljuje, dokler ni najden ključ ali dokler ni izčrpan celoten iskalni prostor.

Kako deluje algoritem binarnega iskanja?

Če želite razumeti delovanje binarnega iskanja, si oglejte naslednjo sliko:

Razmislite o nizu arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , in cilj = 23 .

Prvi korak: Izračunajte sredino in primerjajte srednji element s ključem. Če je ključ nižji od sredine elementa, se premaknite v levo in če je večji od sredine, premaknite iskalni prostor v desno.

  • Ključ (tj. 23) je večji od trenutnega srednjega elementa (tj. 16). Iskalni prostor se premakne v desno.

Algoritem binarnega iskanja: Primerjaj ključ s 16

  • Tipka je nižja od trenutne sredine 56. Iskalni prostor se premakne v levo.

Algoritem binarnega iskanja: Primerjaj ključ s 56

Drugi korak: Če se ključ ujema z vrednostjo srednjega elementa, je element najden in iskanje ustavljeno.

Algoritem binarnega iskanja : ključna ujemanja s sredino

Priporočena praksa Binarno iskanje Poskusite!

The Algoritem binarnega iskanja se lahko izvede na naslednja dva načina

  • Algoritem iterativnega binarnega iskanja
  • Algoritem rekurzivnega binarnega iskanja

Spodaj so podane psevdokode za pristope.

Algoritem iterativnega binarnega iskanja:

Tukaj uporabljamo zanko while za nadaljevanje postopka primerjave ključa in razdelitve iskalnega prostora na dve polovici.

Implementacija algoritma iterativnega binarnega iskanja:

C++ 
// C++ program to implement iterative Binary Search #include  using namespace std; // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, x);  (result == -1)  ? cout << 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement iterative Binary Search #include  // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (result == -1) ? printf('Element is not present'  ' in array')  : printf('Element is present at '  'index %d',  result);  return 0; }>
Java 
// Java implementation of iterative Binary Search import java.io.*; class BinarySearch {    // Returns index of x if it is present in arr[].  int binarySearch(int arr[], int x)  {  int low = 0, high = arr.length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void main(String args[])  {  BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, x);  if (result == -1)  System.out.println(  'Element is not present in array');  else  System.out.println('Element is present at '  + 'index ' + result);  } }>
Python 
# Python3 code to implement iterative Binary # Search. # It returns location of x in given array arr def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - low) // 2 # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: low = mid + 1 # If x is smaller, ignore right half else: high = mid - 1 # If we reach here, then the element # was not present return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>
C# 
// C# implementation of iterative Binary Search using System; class GFG {    // Returns index of x if it is present in arr[]  static int binarySearch(int[] arr, int x)  {  int low = 0, high = arr.Length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void Main()  {  int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, x);  if (result == -1)  Console.WriteLine(  'Element is not present in array');  else  Console.WriteLine('Element is present at '  + 'index ' + result);  } }>
Javascript 
// Program to implement iterative Binary Search   // A iterative binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1  function binarySearch(arr, x) {   let low = 0;  let high = arr.length - 1;  let mid;  while (high>= nizko) { sredina = nizko + Math.floor((visoko - nizko) / 2);    // Če je element prisoten na sredini // sam if (arr[mid] == x) return mid;    // Če je element manjši od mid, potem // je lahko prisoten le v levem podnizu, če (arr[mid]> x) high = mid - 1;    // Sicer je element lahko prisoten samo // v desni podmatrici else low = mid + 1;  } // Sem pridemo, ko element ni // prisoten v matriki return -1; } arr =nova matrika(2, 3, 4, 10, 40);  x = 10;  n = arr.dolžina;  rezultat = binarnoIskanje(arr, x);   (rezultat == -1) ? console.log('Element ni prisoten v nizu') : console.log ('Element je prisoten na indeksu ' + rezultat);   // To kodo sta prispevala simranarora5sos in rshuklabbb>
PHP 
 // PHP program to implement // iterative Binary Search // An iterative binary search  // function function binarySearch($arr, $low, $high, $x) { while ($low <= $high) { $mid = $low + ($high - $low) / 2; // Check if x is present at mid if ($arr[$mid] == $x) return floor($mid); // If x greater, ignore // left half if ($arr[$mid] < $x) $low = $mid + 1; // If x is smaller,  // ignore right half else $high = $mid - 1; } // If we reach here, then  // element was not present return -1; } // Driver Code $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is not present in array'; else echo 'Element is present at index ', $result; // This code is contributed by anuj_67. ?>>
Izhod 
Element is present at index 3>

Časovna zapletenost: O(log N)
Pomožni prostor: O(1)

Algoritem rekurzivnega binarnega iskanja:

Ustvarite rekurzivno funkcijo in primerjajte sredino iskalnega prostora s ključem. In na podlagi rezultata vrne indeks, kjer je bil najden ključ, ali pokliči rekurzivno funkcijo za naslednji iskalni prostor.

Implementacija algoritma rekurzivnega binarnega iskanja:

C++ 
#include  using namespace std; // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= nizko) { int sredina = nizko + (visoko - nizko) / 2;  // Če je element prisoten na sredini // sam if (arr[mid] == x) return mid;  // Če je element manjši od mid, potem // je lahko prisoten le v levi podmatrici, če (arr[mid]> x) vrne binarySearch(arr, low, mid - 1, x);  // Sicer je element lahko prisoten samo // v desni podmatrici return binarySearch(arr, mid + 1, high, x);  } } // Koda gonilnika int main() { int arr[] = { 2, 3, 4, 10, 40 };  int poizvedba = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int rezultat = binarySearch(arr, 0, n - 1, poizvedba);  (rezultat == -1) ? cout<< 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement recursive Binary Search #include  // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= nizko) { int sredina = nizko + (visoko - nizko) / 2;  // Če je element prisoten na sredini // sam if (arr[mid] == x) return mid;  // Če je element manjši od mid, potem // je lahko prisoten le v levi podmatrici, če (arr[mid]> x) vrne binarySearch(arr, low, mid - 1, x);  // Sicer je element lahko prisoten le // v desni podmatrici return binarySearch(arr, mid + 1, high, x);  } // Sem pridemo, ko element ni // prisoten v matriki return -1; } // Koda gonilnika int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int rezultat = binarySearch(arr, 0, n - 1, x);  (rezultat == -1) ? printf('Element ni prisoten v nizu') : printf('Element je prisoten pri indeksu %d', rezultat);  vrni 0; }>
Java 
// Java implementation of recursive Binary Search class BinarySearch {  // Returns index of x if it is present in arr[low..  // high], else return -1  int binarySearch(int arr[], int low, int high, int x)  {  if (high>= nizko) { int sredina = nizko + (visoko - nizko) / 2;  // Če je element prisoten na // sami sredini if ​​(arr[mid] == x) return mid;  // Če je element manjši od mid, potem // je lahko prisoten le v levi podmatrici, če (arr[mid]> x) vrne binarySearch(arr, low, mid - 1, x);  // Sicer je element lahko prisoten le // v desni podmatrici return binarySearch(arr, mid + 1, high, x);  } // Sem pridemo, ko element ni prisoten // v matriki return -1;  } // Koda gonilnika public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int rezultat = ob.binarySearch(arr, 0, n - 1, x);  if (rezultat == -1) System.out.println( 'Element ni prisoten v nizu');  else System.out.println( 'Element je prisoten na indeksu ' + rezultat);  } } /* To kodo je prispeval Rajat Mishra */>
Python 
# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch(arr, low, high, x): # Check base case if high>= low: mid = low + (high - low) // 2 # Če je element prisoten na sami sredini if ​​arr[mid] == x: return mid # Če je element manjši od mid, potem je # lahko le prisoten v levi podmatrici elif arr[mid]> x: vrni binarySearch(arr, low, mid-1, x) # Sicer je element lahko prisoten samo # v desni podmatrisi else: vrni binarySearch(arr, mid + 1, high, x ) # Element ni prisoten v matriki else: return -1 # Koda gonilnika if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Rezultat klica funkcije = binarySearch( arr, 0, len(arr)-1, x) if result != -1: print('Element je prisoten v indeksu', rezultat) else: print('Element ni prisoten v nizu')>
C# 
// C# implementation of recursive Binary Search using System; class GFG {  // Returns index of x if it is present in  // arr[low..high], else return -1  static int binarySearch(int[] arr, int low, int high, int x)  {  if (high>= nizko) { int sredina = nizko + (visoko - nizko) / 2;  // Če je element prisoten na // sami sredini if ​​(arr[mid] == x) return mid;  // Če je element manjši od mid, potem // je lahko prisoten le v levi podmatrici, če (arr[mid]> x) vrne binarySearch(arr, low, mid - 1, x);  // Sicer je element lahko prisoten le // v desni podmatrici return binarySearch(arr, mid + 1, high, x);  } // Sem pridemo, ko element ni prisoten // v matriki return -1;  } // Koda gonilnika public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int rezultat = binarySearch(arr, 0, n - 1, x);  if (rezultat == -1) Console.WriteLine( 'Element ni prisoten v arrau');  else Console.WriteLine('Element je prisoten na indeksu ' + rezultat);  } } // To kodo je prispeval Sam007.>
Javascript 
// JavaScript program to implement recursive Binary Search // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 function binarySearch(arr, low, high, x){  if (high>= nizko) { pusti sredino = nizko + Math.floor((visoko - nizko) / 2);  // Če je element prisoten na sredini // sam if (arr[mid] == x) return mid;  // Če je element manjši od mid, potem // je lahko prisoten le v levi podmatrici, če (arr[mid]> x) vrne binarySearch(arr, low, mid - 1, x);  // Sicer je element lahko prisoten le // v desni podmatrici return binarySearch(arr, mid + 1, high, x);  } // Sem pridemo, ko element ni // prisoten v matriki return -1; } let arr = [ 2, 3, 4, 10, 40 ]; naj bo x = 10; naj n = arr.length naj rezultat = binarySearch(arr, 0, n - 1, x); (rezultat == -1) ? console.log( 'Element ni prisoten v nizu') : console.log('Element je prisoten na indeksu ' +rezultat);>
PHP 
 // PHP program to implement // recursive Binary Search // A recursive binary search // function. It returns location // of x in given array arr[low..high]  // is present, otherwise -1 function binarySearch($arr, $low, $high, $x) { if ($high>= $low) { $mid = ceil($low + ($high - $low) / 2); // Če je element prisoten // na sami sredini if ​​($arr[$mid] == $x) return floor($mid); // Če je element manjši od // mid, potem je lahko // prisoten le v levem podnizu, če ($arr[$mid]> $x) vrne binarySearch($arr, $low, $mid - 1, $x ); // Sicer je lahko element prisoten samo // v desni podmatrici return binarySearch($arr, $mid + 1, $high, $x); } // Sem pridemo, ko element // ni prisoten v matriki return -1; } // Koda gonilnika $arr = array(2, 3, 4, 10, 40); $n = štetje($arr); $x = 10; $rezultat = binarnoIskanje($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element ni prisoten v nizu'; else echo 'Element je prisoten na indeksu ', $result; ?>>
Izhod 
Element is present at index 3>
  • Časovna zapletenost:
    • Najboljši primer: O(1)
    • Povprečni primer: O(log N)
    • Najslabši primer: O(log N)
  • Pomožni prostor: O(1), če upoštevamo sklad rekurzivnih klicev, bo pomožni prostor O(logN).
  • Binarno iskanje se lahko uporablja kot gradnik za kompleksnejše algoritme, ki se uporabljajo pri strojnem učenju, kot so algoritmi za usposabljanje nevronskih mrež ali iskanje optimalnih hiperparametrov za model.
  • Uporablja se lahko za iskanje v računalniški grafiki, kot so algoritmi za sledenje žarkom ali preslikavo teksture.
  • Lahko se uporablja za iskanje po bazi podatkov.
  • Binarno iskanje je hitrejše od linearnega iskanja, zlasti pri velikih nizih.
  • Učinkovitejši od drugih iskalnih algoritmov s podobno časovno kompleksnostjo, kot je interpolacijsko iskanje ali eksponentno iskanje.
  • Binarno iskanje je zelo primerno za iskanje velikih naborov podatkov, ki so shranjeni v zunanjem pomnilniku, na primer na trdem disku ali v oblaku.
  • Niz mora biti razvrščen.
  • Binarno iskanje zahteva, da je podatkovna struktura, ki jo iščete, shranjena na sosednjih pomnilniških lokacijah.
  • Binarno iskanje zahteva, da so elementi matrike primerljivi, kar pomeni, da jih je mogoče razvrstiti.

Pogosto zastavljena vprašanja (FAQ) o binarnem iskanju:

1. Kaj je binarno iskanje?

Binarno iskanje je učinkovit algoritem za iskanje ciljne vrednosti v razvrščeni matriki. Deluje tako, da interval iskanja večkrat razdeli na polovico.

2. Kako deluje binarno iskanje?

Binarno iskanje primerja ciljno vrednost s srednjim elementom matrike. Če sta enaka, je iskanje uspešno. Če je cilj nižji od srednjega elementa, se iskanje nadaljuje v spodnji polovici polja. Če je cilj večji, se iskanje nadaljuje v zgornji polovici. Ta postopek se ponavlja, dokler cilj ni najden ali dokler ni iskalni interval prazen.

3. Kakšna je časovna zapletenost binarnega iskanja?

Časovna kompleksnost binarnega iskanja je O(log2n), kjer je n število elementov v matriki. To je zato, ker se velikost iskalnega intervala v vsakem koraku prepolovi.

4. Kateri so predpogoji za binarno iskanje?

Binarno iskanje zahteva, da je matrika razvrščena v naraščajočem ali padajočem vrstnem redu. Če matrika ni razvrščena, ne moremo uporabiti binarnega iskanja za iskanje elementa v matriki.

5. Kaj se zgodi, če matrika ni razvrščena za binarno iskanje?

Če matrika ni razvrščena, lahko binarno iskanje vrne napačne rezultate. Zanaša se na razvrščeno naravo matrike, da se odloči, katero polovico matrike naj išče.

6. Ali je mogoče binarno iskanje uporabiti za neštevilske podatke?

Da, binarno iskanje je mogoče uporabiti za neštevilske podatke, če obstaja določen vrstni red za elemente. Uporablja se lahko na primer za iskanje nizov po abecednem vrstnem redu.

7. Katere so nekatere pogoste slabosti binarnega iskanja?

Pomanjkljivost binarnega iskanja je, da je treba vhodno polje razvrstiti, da se odloči, v kateri polovici lahko leži ciljni element. Zato moramo za nerazvrščene nize razvrstiti niz, preden uporabimo binarno iskanje.

8. Kdaj je treba uporabiti binarno iskanje?

Pri iskanju ciljne vrednosti v razvrščeni matriki je treba uporabiti binarno iskanje, zlasti če je matrika velika. V primerjavi z linearnimi iskalnimi algoritmi je še posebej učinkovit za velike nabore podatkov.

9. Ali je binarno iskanje mogoče izvajati rekurzivno?

Da, binarno iskanje je mogoče izvajati tako iterativno kot rekurzivno. Rekurzivna izvedba pogosto vodi do bolj jedrnate kode, vendar ima lahko nekoliko višje stroške zaradi rekurzivnega prostora sklada ali klicev funkcij.

10. Ali je binarno iskanje vedno najboljša izbira za iskanje v razvrščenem nizu?

Medtem ko je binarno iskanje zelo učinkovito pri iskanju v razvrščenih nizih, lahko obstajajo posebni primeri, ko so drugi iskalni algoritmi primernejši, na primer pri majhnih naborih podatkov ali ko se niz pogosto spreminja.

matrično množenje v c

Povezani članki:

  • Binarno iskanje na Answer Tutorial s težavami
  • Linearno iskanje proti binarnemu iskanju
  • Kako prepoznati in rešiti težave z binarnim iskanjem?