Før vi lærer binær søgning, lad os lære:
Hvad er søgning?
Søgning er et hjælpeprogram, der gør det muligt for brugeren at finde dokumenter, filer, medier eller enhver anden type data, der opbevares i en database. Søgning fungerer på det enkle princip at matche kriterierne med posterne og vise det for brugeren. På denne måde fungerer den mest basale søgefunktion.
Hvad er binær søgning?
En binær søgning er en avanceret type søgealgoritme, der finder og henter data fra en sorteret liste over emner. Dets vigtigste arbejdsprincip indebærer at dele dataene på listen til halvdelen, indtil den krævede værdi er lokaliseret og vises for brugeren i søgeresultatet. Binær søgning er almindeligt kendt som en halvintervalssøgning eller en logaritmisk søgning .
I denne algoritmevejledning lærer du:
- Hvad er søgning?
- Hvad er binær søgning?
- Hvordan fungerer binær søgning?
- Eksempel på binær søgning
- Hvorfor har vi brug for binær søgning?
Hvordan fungerer binær søgning?
Den binære søgning fungerer på følgende måde:
- Søgningsprocessen starter ved at finde det midterste element i det sorterede dataarray
- Derefter sammenlignes nøgleværdien med elementet
- Hvis nøgleværdien er mindre end det midterste element, analyserer søgninger de øverste værdier til det midterste element til sammenligning og matchning
- Hvis nøgleværdien er større end det midterste element, analyserer de søgninger de lavere værdier til det midterste element til sammenligning og matching
Eksempel på binær søgning
Lad os se på eksemplet på en ordbog. Hvis du har brug for at finde et bestemt ord, går ingen gennem hvert ord på en rækkefølge, men finder tilfældigt de nærmeste ord for at søge efter det krævede ord.
Ovenstående billede illustrerer følgende:
- Du har en matrix på 10 cifre, og elementet 59 skal findes.
- Alle elementerne er markeret med indekset fra 0 - 9. Nu beregnes midten af arrayet. For at gøre dette tager du indeksets venstre og højre værdi og deler dem med 2. Resultatet er 4,5, men vi tager gulvværdien. Derfor er midten 4.
- Algoritmen falder alle elementerne fra midten (4) til den laveste grænse, fordi 59 er større end 24, og nu er arrayet kun tilbage med 5 elementer.
- Nu er 59 større end 45 og mindre end 63. Den midterste er 7. Derfor bliver den højre indeksværdi midt - 1, hvilket er lig med 6, og den venstre indeksværdi forbliver den samme som før, hvilket er 5.
- På dette tidspunkt ved du, at 59 kommer efter 45. Derfor bliver det venstre indeks, som er 5, også midt i.
- Disse gentagelser fortsætter, indtil arrayet kun reduceres til et element, eller det element, der skal findes, bliver midten af arrayet.
Eksempel 2
Lad os se på følgende eksempel for at forstå, at binær søgning fungerer
- Du har en række sorterede værdier fra 2 til 20 og skal finde 18.
- Gennemsnittet af de nedre og øvre grænser er (l + r) / 2 = 4. Den søgte værdi er større end midten, som er 4.
- Arrayværdierne mindre end midten bortkastes fra søgning, og der søges efter værdier, der er større end mellemværdien 4.
- Dette er en tilbagevendende delingsproces, indtil den aktuelle vare, der skal søges, findes.
Hvorfor har vi brug for binær søgning?
Følgende årsager gør binær søgning til et bedre valg til brug som søgealgoritme:
- Binær søgning fungerer effektivt på sorterede data uanset størrelsen på dataene
- I stedet for at udføre søgningen ved at gå gennem dataene i en sekvens, får den binære algoritme tilfældigt adgang til dataene for at finde det krævede element. Dette gør søgecyklusser kortere og mere præcise.
- Binær søgning udfører sammenligninger af de sorterede data baseret på et bestillingsprincip end ved brug af ligestillingssammenligninger, som er langsommere og for det meste unøjagtige.
- Efter hver søgecyklus opdeler algoritmen størrelsen på arrayet i halvdelen, og i den næste iteration fungerer den kun i den resterende halvdel af arrayet
Resumé
- Søgning er et hjælpeprogram, der gør det muligt for brugeren at søge efter dokumenter, filer og andre typer data. En binær søgning er en avanceret type søgealgoritme, der finder og henter data fra en sorteret liste over emner.
- Binær søgning er almindeligt kendt som en halvintervalssøgning eller en logaritmisk søgning
- Det fungerer ved at opdele arrayet i halvdelen på hver iteration under det krævede element findes.
- Den binære algoritme tager midten af arrayet ved at dividere summen af indeksværdierne til venstre og højre med 2. Nu falder algoritmen enten den nedre eller øvre grænse for elementer fra midten af arrayet afhængigt af det element, der skal findes .
- Algoritmen får tilfældig adgang til dataene for at finde det krævede element. Dette gør søgecyklusser kortere og mere præcise.
- Binær søgning udfører sammenligninger af de sorterede data baseret på et bestillingsprincip end ved brug af ligestillingssammenligninger, der er langsomme og unøjagtige.
- En binær søgning er ikke egnet til usorterede data.