ei edes päiväpassia, kun ei tarvitse etsiä arjesta jotain, autonavaimia, kirjoja, kynää, mobiililaturia ja mitä ei. Sama on tietokoneen elämä, siihen on tallennettu niin paljon dataa, että aina kun käyttäjä pyytää jotain dataa, tietokoneen on etsittävä sen muistista tietoja ja annettava ne käyttäjän saataville. Ja tietokoneessa on omat tekniikat etsiä sen muistia nopeasti, josta voit oppia lisää meidän käyttöjärjestelmän opetusohjelma sarja.
mitä jos täytyy kirjoittaa ohjelma, jolla voi etsiä tiettyä lukua jonossa? Miten aiot tehdä sen?
no, tietyn joukon alkuaineen etsimiseen on olemassa kaksi suosittua algoritmia:
- Lineaarihaku
- Binäärihaku
Lineaarihaku
Lineaarihaku on hyvin perus-ja yksinkertainen hakualgoritmi. Lineaarihaussa etsitään tiettyä alkuainetta tai arvoa tietystä jonosta kulkemalla jonon alusta, kunnes haluttu alkuaine tai arvo löytyy.
se vertaa etsittävää alkuainetta kaikkiin matriisissa esiintyviin alkuaineisiin ja kun alkuaine sovitetaan onnistuneesti yhteen, se palauttaa joukon alkuaineen indeksin, muuten se palaa -1.
lineaarista hakua sovelletaan järjestämättömillä tai järjestämättömillä luetteloilla, kun luettelossa on vähemmän elementtejä.
lineaarisen hakualgoritmin ominaisuudet
- sitä käytetään lajittelemattomaan ja järjestämättömään pieneen alkuaineluetteloon.
- sen aikakompleksisuus on O (n), eli aika on lineaarisesti riippuvainen alkuaineiden määrästä, mikä ei ole huono, mutta ei myöskään kovin hyvä.
- sen toteutus on hyvin yksinkertainen.
toteutamme lineaarisen hakualgoritmin seuraavassa opetusohjelmassa.
Binäärihakua
Binäärihakua käytetään lajitellun joukon tai listan kanssa. Binäärihaussa noudatamme seuraavia vaiheita:
- aloitetaan vertaamalla etsittävää alkuainetta luettelon/joukon keskellä olevaan alkuaineeseen.
- jos saamme osuman, palautamme keskimmäisen elementin indeksin.
- jos emme saa osumaa, Tarkistamme, onko etsittävä Elementti arvoltaan pienempi vai suurempi kuin keskimmäinen Elementti.
- jos etsittävä alkio/luku on arvoltaan suurempi kuin keskimmäinen luku, valitsemme alkiot keskimmäisen alkioluvun oikealta puolelta (koska luettelo/joukko on järjestetty, siten oikealla on kaikki keskimmäistä lukua suuremmat numerot), ja aloitamme uudelleen vaiheesta 1.
- jos etsittävä alkuaine/luku on arvoltaan pienempi kuin keskimmäinen luku, valitaan alkuaineet keskimmäisen elementin vasemmalta puolelta ja aloitetaan uudelleen vaiheesta 1.
Binäärihaku on hyödyllinen, kun joukon alkuaineita on suuri määrä ja ne lajitellaan.
joten välttämätön edellytys binäärihaun toimimiselle on, että lista/array on järjestettävä.
binäärihaun ominaisuudet
- on hienoa etsiä suuria lajiteltuja ryhmiä.
- sen aikakompleksisuus on O (log n), joka on erittäin hyvä aikakompleksisuus. Keskustelemme tästä yksityiskohtaisesti Binary Search opetusohjelma.
- sillä on yksinkertainen toteutus.