Binaarse ja lineaarse otsingu erinevus

Binaarne otsing vs lineaarne otsing

Lineaarne otsing, mida nimetatakse ka järjestikuseks otsinguks, on lihtsaim otsingu algoritm. See otsib loendis kindlaksmääratud väärtust, kontrollides loendi kõiki elemente. Binaarne otsing on ka meetod, mida kasutatakse määratud väärtuse leidmiseks sorteeritud loendis. Binaarne otsingumeetod vähendab kontrollitud elementide arvu (igas iteratsioonis), vähendades antud üksuse loendis leidmiseks kuluvat aega.

Mis on lineaarne otsing?

Lineaarne otsing on lihtsaim otsimismeetod, mis kontrollib loendi kõiki elemente järjestikku, kuni see leiab määratud elemendi. Lineaarse otsingumeetodi sisendiks on jada (näiteks massiiv, kogum või string) ja üksus, mida tuleb otsida. Väljund on tõene, kui määratud element on antud jadas, või vale, kui see pole selles jadas. Kuna see meetod kontrollib kõiki loendi üksusi, kuni täpsustatud üksus leitakse, läbib see halvimal juhul kõik loendi elemendid, enne kui leiab vajaliku elemendi. Lineaarse otsingu keerukus on o (n). Seetõttu peetakse seda liiga aeglaseks kasutamiseks elementide otsimisel suurtest loenditest. Kuid see on väga lihtne ja hõlpsamini rakendatav.

Mis on binaarne otsing?

Binaarne otsing on ka meetod, mida kasutatakse sorditud loendis määratud üksuse leidmiseks. Selle meetodi alguses võrreldakse otsitavat elementi loendi keskel asuvate elementidega. Kui võrdlus teeb kindlaks, et kaks elementi on võrdsed, peatub meetod ja tagastab elemendi positsiooni. Kui otsitav element on suurem kui keskmine element, käivitab see meetodi uuesti, kasutades ainult sorteeritud loendi alumist poolt. Kui otsitav element on väiksem kui keskmine element, käivitab see meetodi uuesti, kasutades ainult sorteeritud loendi ülemist poolt. Kui otsitud element ei kuulu loendisse, tagastab meetod kordumatu väärtuse, mis seda näitab. Seetõttu vähendab binaarne otsingumeetod võrdletavate tulemuste põhjal poole võrra võrreldavate elementide arvu (igas iteratsioonis). Järelikult töötab binaarne otsing logaritmilises ajas, mille tulemuseks on o (log n) juhtumi keskmine jõudlus.

Mis vahe on binaarsel ja lineaarsel otsingul??

Ehkki nii lineaarotsing kui ka kahendotsing on otsimismeetodid, on neil mitmeid erinevusi. Kui kahendotsing töötab sorteeritud loendites, saab liinilaevaotsing töötada ka sortimata loendites. Loendi sortimisel on tavaliselt juhtumi keerukus n log n. lineaarset otsimist on lihtne ja arusaadav rakendada kui kahendotsingut. Kuid lineaarne otsing on suurte loendite jaoks liiga aeglane, kuna selle juhtumi keskmine jõudlus on o (n). Teisest küljest peetakse binaarset otsingut tõhusamaks meetodiks, mida saaks kasutada suurte loendite korral. Kuid binaarse otsingu rakendamine võib olla üsna keeruline ja uuring on näidanud, et täpse koodi binaarse otsingu jaoks võib leida vaid viiest kahekümnest raamatust.