Yksi tietojenkäsittelytieteen perusalgoritmeista on binaarihakualgoritmi. Voit toteuttaa binaarihaun kahdella menetelmällä: iteratiivisella menetelmällä ja rekursiivisella menetelmällä. Vaikka molemmilla menetelmillä on sama aikamonimutkaisuus, iteratiivinen menetelmä on paljon tehokkaampi tilan monimutkaisuuden kannalta.

Iteratiivisella menetelmällä on avaruuden monimutkaisuus O(1) verrattuna O (kirjaudu sisään) tuotetaan rekursiivisella menetelmällä. Joten kuinka voit toteuttaa binaarihakualgoritmin iteratiivisella menetelmällä C-, C++- ja Pythonissa?

Mikä on binäärihaku?

Binäärihaku, joka tunnetaan myös nimellä puolivälihaku, logaritminen haku tai binäärihaku, on algoritmi, joka etsii ja palauttaa elementin sijainnin lajitetussa taulukossa. Hakuelementtiä verrataan keskimmäiseen elementtiin. Kun otetaan ala- ja ylärajan keskiarvo, löydät keskielementit.

Jos hakuelementti on suurempi kuin keskimmäinen elementti, se tarkoittaa, että kaikki vasemmalla puolella olevat elementit ovat pienempiä kuin hakuelementti. Ohjaus siirtyy siis taulukon oikealle puolelle (jos taulukko on nousevassa järjestyksessä) nostamalla alarajaa keskielementin seuraavaan kohtaan.

instagram viewer

Vastaavasti, jos hakuelementti on pienempi kuin keskielementti, se tarkoittaa, että kaikki oikealla puolella olevat elementit ovat suurempia kuin hakuelementti. Ohjaus siirtyy siis taulukon vasempaan osaan muuttamalla ylärajaa keskielementin edelliseen paikkaan.

Tämä vähentää vertailujen määrää huomattavasti verrattuna lineaarisen haun toteutus jossa vertailujen määrä on yhtä suuri kuin pahimman mahdollisen skenaarion elementtien lukumäärä. Tämä menetelmä osoittautuu erittäin hyödylliseksi etsittäessä numeroita puhelinmuistiosta tai sanoja sanakirjasta.

Tässä on kaaviomainen esitys Binäärihakualgoritmi:

Binäärihaku käyttäen C

Noudata näitä ohjeita ottaaksesi binaarihaun käyttöön C: llä:

Binaarihakuohjelman koko lähdekoodi C-, C++-, Java- ja Python-käyttäjillä on tässä GitHub-arkisto.

Ohjelma määrittelee funktion, binäärihaku(), joka palauttaa joko löydetyn arvon indeksin tai -1 jos se ei ole läsnä:

#sisältää <stdio.h>
intbinäärihaku(int arr[], int arr_size, int hakunumero){
/*... */
}

Toiminto toimii iteratiivisesti kaventamalla hakuavaruutta. Koska binäärihaku toimii järjestetyissä taulukoissa, voit laskea keskikohdan, joka muuten ei ole järkevää. Voit joko pyytää käyttäjältä lajiteltua taulukkoa tai käyttää lajittelualgoritmeja, kuten kupla- tai valintalajittelu.

The matala ja korkea muuttujat tallentavat indeksit, jotka edustavat nykyisen hakutilan rajoja. mid tallentaa indeksin keskelle:

int matala = 0, korkea = arr_size - 1, keski;

Pää sillä aikaa() silmukka kaventaa hakutilaa. Jos matalan indeksin arvosta tulee koskaan suurempi kuin korkean indeksin arvo, hakutila on käytetty loppuun, joten arvoa ei voi olla olemassa.

sillä aikaa (matala <= korkea) {
/* jatkuu... [1] */
 }
palata-1;

Keskipisteen päivittämisen jälkeen silmukan alussa on kolme mahdollista tulosta:

  1. Jos keskipisteen arvo on se, jota etsimme, palauta tämä indeksi.
  2. Jos keskipisteen arvo on suurempi kuin etsimämme, pienennä korkeaa arvoa.
  3. Jos keskipisteen arvo on pienempi, lisää alinta. 
/* [1] ...jatkuu */
 keski = (matala + (korkea - matala)) / 2;
jos (arr[mid] == hakunumero)
palata keski;
muujos (arr[mid] > search_number)
 korkea = keski - 1;
muu
 matala = keski + 1;

Testaa toimintoa käyttäjän syötteellä. Käyttää scanf() saadaksesi syötettä komentoriviltä, ​​mukaan lukien taulukon koko, sisältö ja haettava numero:

intpää(){
int arr[100], i, arr_size, search_number;
 printf("Anna elementtien lukumäärä: ");
 scanf("%d", &arr_size);
 printf("Anna numerot: ");
for (i = 0; i < arr_size; i++) {
 scanf("%d", &arr[i]);
 }


printf("Anna haettava numero: ");
 scanf("%d", &haku_numero);


i = binäärihaku (arr, arr_size, search_number);


jos (i==-1)
 printf("Numero puuttuu");
muu
 printf("Numero on sijainnissa %d", i + 1);
palata0;
}

Jos löydät numeron, näytä sen sijainti tai indeksi, muussa tapauksessa viesti, jonka mukaan numeroa ei ole.

Binäärihaku C++:lla

Voit muuntaa C-ohjelman C++-ohjelmaksi tuomalla Input Output Stream ja käytä nimiavaruutta std välttääksesi sen toistamisen useita kertoja ohjelman aikana.

#sisältää <iostream>
käyttämällä nimiavaruusstd;

Käyttää cout poistooperaattorin kanssa << sijasta printf() ja cin lisäysoperaattorilla >> sijasta scanf() ja C++-ohjelmasi on valmis.

printf("Anna elementtien lukumäärä: ");
cout <<"Anna elementtien lukumäärä: ";
scanf("%d", &arr_size);
cin >> arr_size;

Binäärihaku Pythonilla

Koska Pythonissa ei ole sisäänrakennettua tukea taulukoille, käytä listoja. Määritä funktio, binäärihaku(), joka hyväksyy kolme parametria, luettelon, sen koon ja haettavan numeron:

defbinäärihaku(arr, arr_size, search_number):
 matala = 0
 korkea = arr_size - 1
sillä aikaa matala <= korkea:
 keski = matala + (korkea-matala)//2
 if arr[mid] == hakunumero:
palata mid
elif arr[mid] > search_number:
 korkea = keski - 1
muu:
 alhainen = keski + 1
palata-1

Alusta kaksi muuttujaa, matala ja korkea, joka toimii luettelon ala- ja ylärajana. Käytä C-toteutuksen tapaan a sillä aikaa silmukka, joka kaventaa hakutilaa. Alustaa mid tallentaaksesi luettelon keskiarvon. Python tarjoaa kerrosjakooperaattorin (//), joka tarjoaa suurimman mahdollisen kokonaisluvun.

Tee vertailut ja kavenna hakuavaruutta, kunnes keskiarvo on yhtä suuri kuin hakunumero. Jos hakunumeroa ei löydy, ohjaus palaa -1.

arr_size = int (input("Anna elementtien lukumäärä: "))
arr=[]
Tulosta("Anna numerot: ", loppu ="")
i: lle alueella (0,arr_size):
 arr.append(int(syöttö()))
search_number = int (input("Anna haettava numero: "))
tulos = binäärihaku (arr, arr_size, search_number)
jos tulos == -1:
 Tulosta("Numero puuttuu")
muu:
 print("Numero On läsnä paikassa ", (tulos + 1))

Testaa toimintoa käyttäjän syötteellä. Käyttää input() saadaksesi luettelon koon, sisällön ja haettavan numeron. Käyttää int() kirjoittaaksesi Pythonin oletuksena hyväksymän merkkijonosyötteen kokonaisluvuksi. Voit lisätä numeroita luetteloon käyttämällä liitä() toiminto.

Puhelu binäärihaku() ja välitä argumentit. Jos löydät numeron, näytä sen sijainti tai indeksi, muussa tapauksessa viesti, jonka mukaan numeroa ei ole.

Binaarihakualgoritmin tulos

Seuraava on binaarihakualgoritmin tulos, kun elementti on taulukossa:

Seuraava on binaarihakualgoritmin tulos, kun elementtiä ei ole taulukossa:

Opi perustietorakenteet ja -algoritmit

Haku on yksi ensimmäisistä oppimistasi algoritmeista, ja sitä kysytään usein koodauskilpailuissa, sijoitteluissa ja haastatteluissa. Joitakin muita algoritmeja, jotka sinun tulisi oppia, ovat lajittelu-, hajautus-, dynaaminen ohjelmointi, merkkijonojen sovitus ja primaalisuuden testausalgoritmit.

Lisäksi on tärkeää ymmärtää algoritmien aika- ja tilamonimutkaisuus. Ne ovat yksi tietojenkäsittelytieteen tärkeimmistä käsitteistä minkä tahansa algoritmin tehokkuuden määrittämisessä. Tietorakenteiden ja algoritmien tuntemuksella voit rakentaa parhaat ohjelmat.