Binäärihaku Algoritmi on hakualgoritmi käytetään lajiteltuna taulukon mukaan jakamalla hakuväli toistuvasti puoliksi . Binäärihaun ideana on käyttää tietoa siitä, että taulukko on lajiteltu ja pienentää aikamonimutkaisuus O(log N:ään).

Mikä on binäärihakualgoritmi?

Binäärihaku on hakualgoritmi, jota käytetään etsimään kohdearvon sijainti a:ssa lajiteltu joukko. Se toimii jakamalla hakuväli toistuvasti kahtia, kunnes tavoitearvo löytyy tai väli on tyhjä. Hakuväli puolitetaan vertaamalla kohdeelementtiä hakutilan keskiarvoon.

oho käsitteitä javassa

Binaarihakualgoritmin käyttäminen:

• Tietorakenne on lajiteltava.
• Pääsy mihin tahansa tietorakenteen elementtiin vie jatkuvasti aikaa.

Binäärihakualgoritmi:

Tässä algoritmissa

• Jaa hakutila kahteen puolikkaaseen löytää keskiindeksin mid .

Keskimmäisen indeksin keskikohdan löytäminen binäärihakualgoritmista

• Vertaa hakutilan keskimmäistä elementtiä avaimeen.
• Jos avain löytyy keskimmäisestä elementistä, prosessi lopetetaan.
• Jos avainta ei löydy keskimmäisestä elementistä, valitse kumpaa puoliskoa käytetään seuraavana hakutilana.
  • Jos avain on pienempi kuin keskielementti, vasenta puolta käytetään seuraavaan hakuun.
  • Jos avain on suurempi kuin keskimmäinen elementti, oikeaa puolta käytetään seuraavaan hakuun.
• Tätä prosessia jatketaan, kunnes avain löytyy tai koko hakutila on käytetty loppuun.

Kuinka binäärihakualgoritmi toimii?

Ymmärtääksesi binäärihaun toiminnan, harkitse seuraavaa kuvaa:

Harkitse taulukkoa arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , ja tavoite = 23 .

Ensimmäinen askel: Laske keskiosa ja vertaa keskielementtiä avaimeen. Jos avain on pienempi kuin keskielementti, siirry vasemmalle ja jos se on suurempi kuin keski, siirrä hakutilaa oikealle.

• Avain (eli 23) on suurempi kuin nykyinen keskielementti (eli 16). Hakualue siirtyy oikealle.

Binäärihakualgoritmi: Vertaa avainta 16:een

• Avain on pienempi kuin nykyinen puoliväli 56. Hakuväli siirtyy vasemmalle.

Binäärihakualgoritmi: Vertaa avainta 56:een

Toinen vaihe: Jos avain vastaa keskielementin arvoa, elementti löytyy ja haku lopetetaan.

Binäärihakualgoritmi: Avain vastaa keskiarvoa

Kuinka ottaa käyttöön binäärihakualgoritmi?

The Binäärihakualgoritmi voidaan toteuttaa kahdella seuraavalla tavalla

• Iteratiivinen binäärihakualgoritmi
• Rekursiivinen binäärihakualgoritmi

Alla on esitetty lähestymistapojen pseudokoodit.

Iteratiivinen binäärihakualgoritmi:

Tässä käytämme while-silmukkaa jatkaaksemme avaimen vertailua ja hakutilan jakamista kahteen puolikkaaseen.

Iteratiivisen binaarihakualgoritmin käyttöönotto:

// 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 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 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);  } }>

# 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# 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);  } }>

// 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>= matala) { keski = matala + Math.floor((korkea - matala) / 2);    // Jos elementti on keskellä // itse if (arr[mid] == x) return mid;    // Jos elementti on pienempi kuin mid, niin // se voi olla läsnä vain vasemmassa alijärjestelmässä, jos (arr[mid]> x) high = mid - 1;    // Muutoin elementti voi olla läsnä vain // oikeassa alijärjestelmässä else low = mid + 1;  } // Saavumme tähän kun elementti ei ole // taulukossa return -1; } arr =uusi Array(2, 3, 4, 10, 40);  x = 10;  n = arr.length;  tulos = binarySearch(arr, x);   (tulos == -1) ? console.log('Elementti ei ole taulukossa') : console.log ('Elementti on indeksissä ' + tulos);   // Tämän koodin ovat tuottaneet simranarora5sos ja rshuklabbb>

 // 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. ?>>>  
  Lähtö  
Element is present at index 3>
  
    Aika monimutkaisuus:    O(log N)  
    Aputila:    O(1)
 
    Rekursiivinen binäärihakualgoritmi:    
 
Luo rekursiivinen funktio ja vertaa hakutilan keskikohtaa avaimeen. Ja tuloksen perusteella joko palauta indeksi, josta avain löytyy, tai kutsu seuraavan hakutilan rekursiivista funktiota.
 
Rekursiivisen binaarihakualgoritmin käyttöönotto:
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>= matala) { int mid = matala + (korkea - matala) / 2;  // Jos elementti on keskellä // itse if (arr[mid] == x) return mid;  // Jos elementti on pienempi kuin mid, niin // se voi olla vain vasemmassa alipalkissa, jos (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Muutoin elementti voi olla läsnä vain // oikeassa alitaulukossa return binarySearch(arr, mid + 1, high, x);  } } // Ohjainkoodi int main() { int arr[] = { 2, 3, 4, 10, 40 };  int kysely = 10;  int n = koko(arr) / koko(arr[0]);  int tulos = binarySearch(arr, 0, n - 1, kysely);  (tulos == -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>= matala) { int mid = matala + (korkea - matala) / 2;  // Jos elementti on keskellä // itse if (arr[mid] == x) return mid;  // Jos elementti on pienempi kuin mid, niin // se voi olla vain vasemmassa alipalkissa, jos (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Muutoin elementti voi olla läsnä vain // oikeassa alitaulukossa return binarySearch(arr, mid + 1, high, x);  } // Saavumme tähän kun elementti ei ole // taulukossa return -1; } // Ohjainkoodi int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = koko(arr) / koko(arr[0]);  int x = 10;  int tulos = binarySearch(arr, 0, n - 1, x);  (tulos == -1) ? printf('Elementti ei ole taulukossa') : printf('Elementti on indeksissä %d', tulos);  paluu 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>= matala) { int mid = matala + (korkea - matala) / 2;  // Jos elementti on // itse keskellä if (arr[mid] == x) return mid;  // Jos elementti on pienempi kuin mid, niin // se voi olla vain vasemmassa alipalkissa, jos (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Muutoin elementti voi olla läsnä vain // oikeassa alitaulukossa return binarySearch(arr, mid + 1, high, x);  } // Saavumme tähän kun elementtiä ei ole // taulukossa return -1;  } // Ohjainkoodi 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 tulos = ob.binarySearch(arr, 0, n - 1, x);  if (tulos == -1) System.out.println( 'Elementtiä ei ole taulukossa');  else System.out.println( 'Elementti on indeksissä ' + tulos);  } } /* Tämän koodin on toimittanut 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>= alhainen: keski = matala + (korkea - matala) // 2 # Jos elementti on itse keskellä jos arr[mid] == x: return mid # Jos elementti on pienempi kuin keski, se # voi olla vain läsnä vasemmassa alijärjestelmässä elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # Muutoin elementti voi olla läsnä vain # oikeassa alijärjestelmässä else: return binarySearch(arr, mid + 1, high, x ) # Elementti ei ole taulukossa else: return -1 # Ohjainkoodi if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Funktiokutsun tulos = binarySearch( arr, 0, len(arr)-1, x) jos tulos != -1: print('Elementti on indeksissä', tulos) else: print('Elementti ei ole taulukossa')> 
 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>= matala) { int mid = matala + (korkea - matala) / 2;  // Jos elementti on // itse keskellä if (arr[mid] == x) return mid;  // Jos elementti on pienempi kuin mid, niin // se voi olla vain vasemmassa alipalkissa, jos (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Muutoin elementti voi olla läsnä vain // oikeassa alitaulukossa return binarySearch(arr, mid + 1, high, x);  } // Saavumme tähän kun elementtiä ei ole // taulukossa return -1;  } // Ohjainkoodi public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int tulos = binarySearch(arr, 0, n - 1, x);  if (tulos == -1) Console.WriteLine( 'Elementtiä ei ole arraussa');  else Console.WriteLine('Elementti on indeksissä ' + tulos);  } } // Tämän koodin on toimittanut Sam007.>>Javascript>PHP>>
   
  Lähtö    Binäärihakualgoritmin monimutkaisuusanalyysi:  
    Aika monimutkaisuus:     
Paras tapaus: O(1)
Keskimääräinen tapaus: O(log N)
Huonoin tapaus: O (log N)
    Aputila:    O(1), Jos otetaan huomioon rekursiivinen kutsupino, aputila on O(logN).
     Binäärihakualgoritmin sovellukset:     
Binaarihakua voidaan käyttää rakennuspalikkana monimutkaisemmille koneoppimisessa käytettäville algoritmeille, kuten algoritmeille neuroverkkojen opettamiseen tai mallin optimaalisten hyperparametrien etsimiseen.
Sitä voidaan käyttää etsimiseen tietokonegrafiikasta, kuten säteenseuranta- tai pintakuviointialgoritmeista.
Sitä voidaan käyttää tietokannan etsimiseen.
    Binäärihaun edut:    
Binaarihaku on nopeampi kuin lineaarihaku, etenkin suurille taulukoille.
Tehokkaampi kuin muut hakualgoritmit, joilla on samanlainen aikamonimutkaisuus, kuten interpolaatiohaku tai eksponentiaalinen haku.
Binaarihaku soveltuu hyvin suurten tietojoukkojen etsimiseen, jotka on tallennettu ulkoiseen muistiin, kuten kiintolevylle tai pilveen.
    Binäärihaun haitat:    
Taulukko tulee lajitella.
Binaarihaku edellyttää, että haettava tietorakenne on tallennettu vierekkäisiin muistipaikkoihin.
Binäärihaku edellyttää, että taulukon elementit ovat vertailukelpoisia, eli ne on voitava järjestää.
Usein kysytyt kysymykset (FAQ) binäärihaussa:
1. Mikä on binäärihaku?
 
Binäärihaku on tehokas algoritmi kohdearvon löytämiseen lajitetusta taulukosta. Se toimii jakamalla hakuväli toistuvasti puoliksi.
 
2. Miten binaarihaku toimii?
 
Binaarihaku vertaa kohdearvoa taulukon keskielementtiin. Jos ne ovat yhtä suuret, haku onnistuu. Jos kohde on pienempi kuin keskielementti, haku jatkuu taulukon alaosassa. Jos tavoite on suurempi, haku jatkuu yläpuoliskolla. Tämä prosessi toistuu, kunnes kohde löytyy tai hakuväli on tyhjä.
 
3. Mikä on binaarihaun aikamonimutkaisuus?
 
Binäärihaun aikamonimutkaisuus on O(log2n), jossa n on taulukon elementtien lukumäärä. Tämä johtuu siitä, että hakuvälin koko puolitetaan jokaisessa vaiheessa.
 
4. Mitkä ovat binaarihaun edellytykset?
 
Binäärihaku edellyttää, että taulukko on lajiteltu nousevaan tai laskevaan järjestykseen. Jos taulukkoa ei ole lajiteltu, emme voi käyttää binaarihakua taulukon elementin etsimiseen.
 
5. Mitä tapahtuu, jos taulukkoa ei ole lajiteltu binäärihakua varten?
 
Jos taulukkoa ei ole lajiteltu, binäärihaku saattaa palauttaa virheellisiä tuloksia. Se luottaa taulukon lajiteltuun luonteeseen tehdäkseen päätöksiä siitä, mitä puoliskoa taulukosta etsitään.
 
6. Voidaanko binäärihakua soveltaa ei-numeeriseen dataan?
 
Kyllä, binäärihakua voidaan käyttää ei-numeeriseen dataan niin kauan kuin elementeillä on määritetty järjestys. Sitä voidaan käyttää esimerkiksi merkkijonojen etsimiseen aakkosjärjestyksessä.
 
7. Mitkä ovat binaarihaun yleisiä haittoja?
 
Binaarihaun haittana on, että syötetaulukko on lajiteltava, jotta voidaan päättää, kummassa puoliskossa kohdeelementti voi olla. Siksi lajittelemattomien taulukoiden osalta meidän on lajiteltava taulukko ennen binaarihaun käyttämistä.
 
8. Milloin binaarihakua tulisi käyttää?
 
Binaarihakua tulisi käyttää, kun etsitään kohdearvoa lajiteltusta taulukosta, varsinkin kun taulukon koko on suuri. Se on erityisen tehokas suurille tietojoukoille verrattuna lineaarisiin hakualgoritmeihin.
 
9. Voidaanko binäärihaku toteuttaa rekursiivisesti?
 
Kyllä, binäärihaku voidaan toteuttaa sekä iteratiivisesti että rekursiivisesti. Rekursiivinen toteutus johtaa usein ytimekkäämpään koodiin, mutta sillä voi olla hieman korkeampi lisäkustannus johtuen rekursiivisista pinotilasta tai funktiokutsuista.
 
10. Onko binaarihaku aina paras valinta hakuun järjestetyssä taulukossa?
 
Vaikka binäärihaku on erittäin tehokas haettaessa lajiteltuja taulukoita, saattaa olla erityisiä tapauksia, joissa muut hakualgoritmit ovat sopivampia, kuten kun käsitellään pieniä tietojoukkoja tai kun taulukkoa muutetaan usein.
intellij idea vs eclipse
 
    Aiheeseen liittyvät artikkelit:     
 
 Binaarihaku ongelmiin liittyvien vastausten opetusohjelmassa 
 Lineaarinen haku vs binäärihaku 
 Kuinka tunnistaa ja ratkaista binaarihakuongelmia?