Ennen kuin ymmärrämme lineaarisen ja binaarihaun erot, meidän tulisi ensin tuntea lineaarinen haku ja binäärihaku erikseen.
Mikä on lineaarinen haku?
Lineaarinen haku tunnetaan myös peräkkäisenä hauna, joka yksinkertaisesti skannaa jokaisen elementin kerrallaan. Oletetaan, että haluamme etsiä elementtiä taulukosta tai luettelosta; me yksinkertaisesti laskemme sen pituuden emmekä hyppää mihinkään kohtaan.
Tarkastellaanpa yksinkertaista esimerkkiä.
Oletetaan, että meillä on 10 elementin joukko, kuten alla olevassa kuvassa näkyy:
Yllä oleva kuva esittää merkkityyppien joukon, jossa on 10 arvoa. Jos haluamme etsiä 'E', haku alkaa 0:stathelementtiä ja skannaa jokaista elementtiä, kunnes elementtiä, eli 'E' ei löydy. Emme voi hypätä suoraan nollastathelementti 4theli jokaista elementtiä skannataan yksitellen, kunnes elementtiä ei löydy.
Lineaarisen haun monimutkaisuus
Lineaarihaku skannaa jokaista elementtiä yksitellen, kunnes elementtiä ei löydy. Jos elementtien määrä kasvaa, myös skannattavien elementtien määrä kasvaa. Voimme sanoa, että elementtien etsimiseen kuluva aika on verrannollinen elementtien määrään . Siksi pahimman tapauksen monimutkaisuus on O(n)
Mikä on binaarihaku?
Binäärihaku on haku, jossa keskimmäinen elementti lasketaan sen tarkistamiseksi, onko se pienempi vai suurempi kuin haettava elementti. Binaarihaun käytön tärkein etu on, että se ei skannaa jokaista luettelon elementtiä. Sen sijaan, että se skannaisi jokaisen elementin, se suorittaa haun luettelon puolikkaalle. Joten binäärihaku vie vähemmän aikaa elementin etsimiseen verrattuna lineaarihakuun.
Se yksi binäärihaun edellytys on, että taulukon tulee olla lajiteltuna, kun taas lineaarinen haku toimii sekä lajitetussa että lajittelemattomassa taulukossa. Binäärihakualgoritmi perustuu jakaa ja hallitse -tekniikkaan, mikä tarkoittaa, että se jakaa taulukon rekursiivisesti.
Binäärihaussa käytetään kolmea tapausta:
Tapaus 1: tiedot
Tapaus 2: data>a[mid] sitten right=mid-1
Tapaus 3: data = a[mid] // elementti löytyy
Yllä olevassa tapauksessa ' a ' on taulukon nimi, mid on elementin indeksi, joka lasketaan rekursiivisesti, tiedot on etsittävä elementti, vasemmalle tarkoittaa taulukon vasenta elementtiä ja oikein tarkoittaa elementtiä, joka esiintyy taulukon oikealla puolella.
Ymmärretään binäärihaun toimintaa esimerkin kautta.
Oletetaan, että meillä on 10-koon joukko, joka on indeksoitu 0:sta 9:ään alla olevan kuvan mukaisesti:
Haluamme etsiä 70 elementtiä yllä olevasta taulukosta.
Vaihe 1: Ensin lasketaan taulukon keskielementti. Tarkastellaan kahta muuttujaa, eli vasenta ja oikeaa. Aluksi vasen = 0 ja oikea = 9 alla olevan kuvan mukaisesti:
Keskielementin arvo voidaan laskea seuraavasti:
Siksi mid = 4 ja a[mid] = 50. Haettava elementti on 70, joten a[mid] ei ole yhtä suuri kuin data. Tapaus 2 täyttyy, eli data>a[mid].
Vaihe 2: Datana>a[mid], joten vasemman arvoa kasvatetaan mid+1:llä, eli vasen=mid+1. Keskiarvon arvo on 4, joten vasemman arvosta tulee 5. Nyt meillä on alla olevan kuvan mukainen alitaulukko:
Nyt taas keskiarvo lasketaan käyttämällä yllä olevaa kaavaa, ja keskiarvon arvoksi tulee 7. Nyt keskiarvo voidaan esittää seuraavasti:
Yllä olevassa kuvassa voimme havaita, että a[mid]>data, joten jälleen mid:n arvo lasketaan seuraavassa vaiheessa.
Vaihe 3: A[mid]>-tietona oikeuden arvoa pienennetään 1:n puoliväliin mennessä. Keskiarvon arvo on 7, joten oikean arvoksi tulee 6. Taulukko voidaan esittää seuraavasti:
Keskiarvon arvo lasketaan uudelleen. Vasemman ja oikean arvot ovat 5 ja 6, vastaavasti. Siksi keskiarvon arvo on 5. Nyt keskiarvo voidaan esittää taulukossa alla olevan kuvan mukaisesti:
Yllä olevasta kuvasta voimme havaita, että a[mid]
Vaihe 4: Kuten [keski] Nyt keskiarvon arvo lasketaan uudelleen käyttämällä kaavaa, jota olemme jo käsitelleet. Vasemman ja oikean arvot ovat 6 ja 6, joten keskiarvon arvosta tulee 6 alla olevan kuvan mukaisesti: Voimme havaita yllä olevassa kuvassa, että a[mid]=data. Siksi haku on valmis ja elementti löytyy onnistuneesti. Lineaarihaun ja binäärihaun erot ovat seuraavat: Kuvaus Lineaarinen haku on haku, joka löytää elementin luettelosta etsimällä elementtiä peräkkäin, kunnes elementti löytyy luettelosta. Toisaalta binäärihaku on haku, joka löytää luettelon keskimmäisen elementin rekursiivisesti, kunnes keskimmäinen elementti osuu haettuun elementtiin. Molemmat haut toimivat Lineaarinen haku aloittaa haun ensimmäisestä elementistä ja skannaa elementin kerrallaan siirtymättä seuraavaan elementtiin. Toisaalta binäärihaku jakaa taulukon puoliksi laskemalla taulukon keskielementin. Toteutus Lineaarinen haku voidaan toteuttaa missä tahansa lineaarisessa tietorakenteessa, kuten vektori, yksitellen linkitetty lista, kaksoislinkitetty lista. Sitä vastoin binäärihaku voidaan toteuttaa niissä tietorakenteissa, joissa on kaksisuuntainen läpikulku, eli eteenpäin- ja taaksepäinkulku. Monimutkaisuus Lineaarihakua on helppo käyttää, tai voidaan sanoa, että se on vähemmän monimutkainen, koska lineaarihaun elementit voidaan järjestää mihin tahansa järjestykseen, kun taas binäärihaussa elementit on järjestettävä tiettyyn järjestykseen. Lajiteltuja elementtejä Lineaarihaun elementit voidaan järjestää satunnaiseen järjestykseen. Lineaarisessa haussa ei ole pakollista, että elementit on järjestetty lajiteltuun järjestykseen. Toisaalta binäärihaussa elementit on järjestettävä lajiteltuun järjestykseen. Se voidaan järjestää joko kasvavaan tai laskevaan järjestykseen, ja vastaavasti algoritmi muuttuu. Koska binäärihaku käyttää lajiteltua taulukkoa, elementti on lisättävä oikeaan paikkaan. Sen sijaan lineaarinen haku ei vaadi lajiteltua taulukkoa, jotta uusi elementti voidaan helposti lisätä taulukon loppuun. Lähestyä Lineaarinen haku käyttää iteratiivista lähestymistapaa elementin löytämiseen, joten se tunnetaan myös peräkkäisenä lähestymistavana. Sitä vastoin binäärihaku laskee taulukon keskielementin, joten se käyttää hajota ja hallitse -lähestymistapaa. Tietojoukko Lineaarinen haku ei sovellu suurelle tietojoukolle. Jos haluamme etsiä elementistä, joka on taulukon viimeinen elementti, lineaarinen haku alkaa haun ensimmäisestä elementistä ja jatkuu viimeiseen elementtiin, joten elementin etsimiseen kuluisi paljon aikaa. Toisaalta binäärihaku sopii suurelle tietojoukolle, koska se vie vähemmän aikaa. Nopeus Jos tietojoukko on suuri lineaarisessa haussa, laskentakustannukset olisivat korkeat ja nopeus hidastuu. Jos tietojoukko on suuri binäärihaussa, laskentakustannukset olisivat pienemmät verrattuna lineaarihakuun ja nopeudesta tulee nopea. Mitat Lineaarihakua voidaan käyttää sekä yksi- että moniulotteisessa taulukossa, kun taas binäärihaku voidaan toteuttaa vain yksiulotteisessa taulukossa. Tehokkuus Lineaarinen haku on vähemmän tehokasta, kun otetaan huomioon suuret tietojoukot. Binäärihaku on tehokkaampi kuin lineaarinen haku suurten tietojoukkojen tapauksessa. Katsotaanpa eroja taulukkomuodossa. 
Lineaarihaun ja binaarihaun erot
linuxin virhekoodit
Vertailuperuste Lineaarinen haku Binäärihaku Määritelmä Lineaarinen haku aloittaa haun ensimmäisestä elementistä ja vertaa jokaista elementtiä etsittyyn elementtiin, kunnes elementtiä ei löydy. Se löytää haetun elementin sijainnin etsimällä taulukon keskielementin. Lajiteltu data Lineaarisessa haussa elementtejä ei tarvitse järjestää lajiteltuun järjestykseen. Binäärihaun edellytyksenä on, että elementit on järjestettävä lajiteltuun järjestykseen. Toteutus Lineaarinen haku voidaan toteuttaa missä tahansa lineaarisessa tietorakenteessa, kuten taulukossa, linkitetyssä listassa jne. Binaarihaun toteutus on rajoitettua, koska se voidaan toteuttaa vain niissä tietorakenteissa, joissa on kaksisuuntainen läpikulku. Lähestyä Se perustuu peräkkäiseen lähestymistapaan. Se perustuu hajota ja hallitse -lähestymistapaan. Koko Se on parempi pienikokoisille tietojoukoille. Se on parempi suurikokoisille tietojoukoille. Tehokkuus Se on vähemmän tehokas suurten tietokokonaisuuksien tapauksessa. Se on tehokkaampi suurten tietokokonaisuuksien tapauksessa. Pahimmassa tapauksessa Lineaarisessa haussa pahin skenaario elementin löytämiseksi on O(n). Binäärihaussa pahin skenaario elementin löytämiseksi on O(log2n). Paras skenaario Lineaarisessa haussa paras skenaario listan ensimmäisen elementin löytämiseksi on O(1). Binäärihaussa paras skenaario listan ensimmäisen elementin löytämiseksi on O(1). Dimensionaalinen matriisi Se voidaan toteuttaa sekä yksi- että moniulotteisessa taulukossa. Se voidaan toteuttaa vain moniulotteisessa taulukossa.