Ikke engang en eneste dagspass, når vi ikke trenger å søke etter noe i vårt daglige liv, bilnøkler, bøker, penn, mobil lader og hva ikke. Samme er livet til en datamaskin, det er så mye data lagret i det, at når en bruker ber om noen data, må datamaskinen søke i minnet for å lete etter dataene og gjøre det tilgjengelig for brukeren. Og datamaskinen har sine egne teknikker for å søke gjennom det minnet raskt, som du kan lære mer om i Vår operativsystemopplæringsserie.
Hva om du må skrive et program for å søke et gitt nummer i en matrise? Hvordan vil du gjøre det?
vel, for å søke et element i et gitt array, er det to populære algoritmer tilgjengelig:
- Lineært Søk
- Binært Søk
Lineært Søk
Lineært søk er en veldig enkel og enkel søkealgoritme. I Lineært søk søker vi et element eller en verdi i et gitt array ved å krysse arrayet fra starten, til ønsket element eller verdi er funnet.
den sammenligner elementet som skal søkes med alle elementene som finnes i matrisen, og når elementet matches vellykket, returnerer det indeksen til elementet i matrisen, ellers returnerer den -1.
Lineært Søk brukes på usorterte eller uordnede lister, når det er færre elementer i en liste.
Funksjoner Av Lineær Søkealgoritme
- Den brukes til usortert og uordnet liten liste over elementer.
- Den har en tidskompleksitet På O (n), noe som betyr at tiden er lineært avhengig av antall elementer, noe som ikke er dårlig, men ikke så bra også.
- Den har en veldig enkel implementering.
Vi vil implementere Den Lineære søkealgoritmen i neste opplæring.
Binært Søk
Binært Søk brukes med sortert matrise eller liste. I binært søk følger vi følgende trinn:
- vi starter med å sammenligne elementet som skal søkes med elementet midt i listen / arrayet.
- hvis vi får en kamp, returnerer vi indeksen til midtelementet.
- hvis vi ikke får en kamp, kontrollerer vi om elementet som skal søkes, er mindre eller større enn i verdi enn midtelementet.
- hvis elementet / nummeret som skal søkes, er større i verdi enn mellomnummeret, velger vi elementene på høyre side av midtelementet(som listen/arrayet er sortert, derfor til høyre, vil vi ha alle tallene større enn mellomnummeret), og starter igjen fra trinn 1.
- hvis elementet / nummeret som skal søkes, er mindre i verdi enn midtnummeret, velger vi elementene på venstre side av midtelementet, og starter igjen fra trinn 1.
Binært Søk er nyttig når det er stort antall elementer i en matrise og de sorteres.
så en nødvendig betingelse For At Binært søk skal fungere er at listen / arrayet skal sorteres.
Funksjoner Av Binær Søk
- det er flott å søke gjennom store sorterte arrays.
- Den har en tidskompleksitet På O (log n) som er en veldig god tidskompleksitet. Vi vil diskutere dette i detaljer I Binary Search tutorial.
- Den har en enkel implementering.