Binær søkealgoritme med EKSEMPEL

Før vi lærer binært søk, la oss lære:

Hva er søk?

Søk er et verktøy som gjør det mulig for brukeren å finne dokumenter, filer, media eller andre typer data som holdes inne i en database. Søk fungerer etter det enkle prinsippet å matche kriteriene med postene og vise det til brukeren. På denne måten fungerer den mest grunnleggende søkefunksjonen.

Hva er binært søk?

Et binært søk er en avansert type søkealgoritme som finner og henter data fra en sortert liste med elementer. Dets kjernearbeidsprinsipp innebærer å dele dataene i listen til halvparten til den nødvendige verdien er lokalisert og vist til brukeren i søkeresultatet. Binært søk er ofte kjent som en halvintervallsøk eller logaritmisk søk.

Hvordan fungerer binært søk?

Det binære søket fungerer på følgende måte:

• Søkeprosessen starter ved å lokalisere midtelementet i det sorterte datautvalget
• Deretter sammenlignes nøkkelverdien med elementet
• Hvis nøkkelverdien er mindre enn det midterste elementet, analyserer søk de øvre verdiene til det midterste elementet for sammenligning og matching
• I tilfelle nøkkelverdien er større enn midtelementet, analyserer søk de lavere verdiene til midtelementet for sammenligning og matching

Eksempel på binært søk

La oss se på eksempelet på en ordbok. Hvis du trenger å finne et bestemt ord, går ingen gjennom hvert ord på en sekvensiell måte, men finner tilfeldig de nærmeste ordene for å søke etter det nødvendige ordet.

Bildet ovenfor illustrerer følgende:

1. Du har en matrise med 10 sifre, og elementet 59 må finnes.
2. Alle elementene er merket med indeksen fra 0 – 9. Nå beregnes midten av matrisen. For å gjøre det tar du verdiene lengst til venstre og høyre i indeksen og deler dem på 2. Resultatet er 4.5, men vi tar gulvverdien. Derfor er midten 4.
3. Algoritmen slipper alle elementene fra midten (4) til den laveste grensen fordi 59 er større enn 24, og nå har arrayet kun 5 elementer.
4. Nå er 59 større enn 45 og mindre enn 63. Midten er 7. Derfor blir høyre indeksverdi midt – 1, som tilsvarer 6, og venstre indeksverdi forblir den samme som før, som er 5.
5. På dette tidspunktet vet du at 59 kommer etter 45. Derfor blir venstre indeks, som er 5, også midten.
6. Disse iterasjonene fortsetter til matrisen er redusert til bare ett element, eller elementet som skal finnes blir midt i matrisen.

Eksempel 2

La oss se på følgende eksempel for å forstå at det binære søket fungerer

1. Du har en rekke sorterte verdier fra 2 til 20 og må finne 18.
2. Gjennomsnittet av de nedre og øvre grensene er (l + r) / 2 = 4. Verdien som søkes er større enn midten som er 4.
3. Matriseverdiene som er mindre enn midten blir slettet fra søk og verdier større enn midtverdien 4 blir søkt.
4. Dette er en gjentakende delingsprosess til det faktiske elementet som skal søkes er funnet.

Hvorfor trenger vi binært søk?

Følgende grunner gjør det binære søket til et bedre valg for å brukes som en søkealgoritme:

• Binært søk fungerer effektivt på sorterte data uansett størrelsen på dataene
• I stedet for å utføre søket ved å gå gjennom dataene i en sekvens, får den binære algoritmen tilfeldig tilgang til dataene for å finne det nødvendige elementet. Dette gjør søkesyklusene kortere og mer nøyaktige.
• Binærsøk utfører sammenligninger av de sorterte dataene basert på et bestillingsprinsipp enn å bruke likhetssammenligninger, som er tregere og for det meste unøyaktige.
• Etter hver syklus med søk deler algoritmen størrelsen på matrisen i to, og i neste iterasjon vil den bare fungere i den gjenværende halvdelen av matrisen

Lær vår neste veiledning av Lineært søk: Python, C++ Eksempel

Sammendrag

• Søk er et verktøy som lar brukeren søke etter dokumenter, filer og andre typer data. Et binært søk er en avansert type søkealgoritme som finner og henter data fra en sortert liste med elementer.
• Binært søk er ofte kjent som et halvintervallsøk eller et logaritmisk søk
• Det fungerer ved å dele matrisen i to ved hver iterasjon under det nødvendige elementet som er funnet.
• Ocuco binær algoritme tar midten av matrisen ved å dele summen av indeksverdiene til venstre og lengst til høyre med 2. Nå faller algoritmen enten den nedre eller øvre grensen for elementer fra midten av matrisen, avhengig av elementet som skal finnes.
• Algoritmen får tilfeldig tilgang til dataene for å finne det nødvendige elementet. Dette gjør søkesyklusene kortere og mer nøyaktige.
• Binært søk utfører sammenligninger av de sorterte dataene basert på et bestillingsprinsipp enn å bruke likhetssammenlikninger som er trege og unøyaktige.
• Et binært søk er ikke egnet for usorterte data.