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 på det enkle prinsippet om å 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 over elementer. Dets viktigste arbeidsprinsipp innebærer å dele dataene i listen til halvparten til den nødvendige verdien er lokalisert og vises for brukeren i søkeresultatet. Binært søk er ofte kjent som et halvt intervalsøk eller et logaritmisk søk .
I denne algoritmeopplæringen lærer du:
- Hva er søk?
- Hva er binært søk?
- Hvordan fungerer binært søk?
- Eksempel på binærsøk
- Hvorfor trenger vi binær søk?
Hvordan fungerer binært søk?
Binærsøket fungerer på følgende måte:
- Søkeprosessen starter ved å finne det midterste elementet i den sorterte matrisen med data
- Etter det blir nøkkelverdien sammenlignet med elementet
- Hvis nøkkelverdien er mindre enn det midterste elementet, analyserer søk de øvre verdiene til det midterste elementet for sammenligning og samsvar
- I tilfelle nøkkelverdien er større enn det midterste elementet, analyserer de nedre verdiene til det midterste elementet for sammenligning og samsvar
Eksempel på binærsøk
La oss se på eksemplet 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 ønsket ord.
Ovenstående bilde illustrerer følgende:
- Du har en rekke med 10 sifre, og elementet 59 må finnes.
- Alle elementene er merket med indeksen fra 0 - 9. Nå beregnes midten av matrisen. For å gjøre det tar du venstre og høyre verdi av indeksen og deler dem med 2. Resultatet er 4,5, men vi tar gulvverdien. Derfor er midten 4.
- Algoritmen slipper alle elementene fra midten (4) til den laveste grensen fordi 59 er større enn 24, og nå er matrisen igjen med bare 5 elementer.
- 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.
- På dette tidspunktet vet du at 59 kommer etter 45. Derfor blir venstre indeks, som er 5, også midt.
- Disse iterasjonene fortsetter til matrisen er redusert til bare ett element, eller elementet som blir funnet blir midten av matrisen.
Eksempel 2
La oss se på følgende eksempel for å forstå det binære søket som fungerer
- Du har en rekke sorterte verdier fra 2 til 20 og må finne 18.
- Gjennomsnittet av nedre og øvre grenser er (l + r) / 2 = 4. Verdien som søkes er større enn midten som er 4.
- Arrayverdiene mindre enn midten slippes fra søk og verdier som er større enn midtverdien 4 blir søkt.
- Dette er en tilbakevendende delingsprosess til den faktiske gjenstanden som skal søkes, blir funnet.
Hvorfor trenger vi binær søk?
Følgende grunner gjør det binære søket til et bedre valg å bli brukt 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ært søk utfører sammenligninger av de sorterte dataene basert på et bestillingsprinsipp enn å bruke likestillingssammenligninger, som er langsommere og stort sett unøyaktige.
- Etter hver søkesyklus deler algoritmen størrelsen på matrisen i halvparten, og i neste iterasjon vil den bare fungere i den gjenværende halvdelen av matrisen
Sammendrag
- Søk er et verktøy som gjør det mulig for 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 over elementer.
- Binært søk er ofte kjent som et halvt intervalsøk eller et logaritmisk søk
- Det fungerer ved å dele matrisen i halvparten på hver iterasjon under det nødvendige elementet er funnet.
- Den binære algoritmen tar midten av matrisen ved å dele summen av indeksverdiene til venstre og høyre med 2. Nå faller algoritmen enten nedre eller øvre grense 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 likeverdige sammenligninger som er langsomme og unøyaktige.
- Et binært søk er ikke egnet for usorterte data.