Binær søgealgoritme med EKSEMPEL

Før vi lærer binær søgning, lad os lære:

Hvad er søgning?

Søg er et værktøj, 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 efter det simple princip at matche kriterierne med posterne og vise dem til 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 elementer. Dets kernearbejdsprincip involverer at dele dataene i listen til halvdelen, indtil den ønskede værdi er fundet og vist for brugeren i søgeresultatet. Binær søgning er almindeligvis kendt som en halvintervalsøgning eller logaritmisk søgning.

Hvordan fungerer binær søgning?

Den binære søgning fungerer på følgende måde:

• Søgningsprocessen starter ved at lokalisere det midterste element i den sorterede række af data
• Derefter sammenlignes nøgleværdien med elementet
• Hvis nøgleværdien er mindre end det midterste element, analyserer søgninger de øvre værdier til det midterste element for sammenligning og matchning
• Hvis nøgleværdien er større end det midterste element, analyserer søgninger de lavere værdier til det midterste element for sammenligning og matchning

Eksempel på binær søgning

Lad os se på eksemplet med en ordbog. Hvis du har brug for at finde et bestemt ord, går ingen igennem hvert ord på en sekventiel måde, men finder tilfældigt de nærmeste ord for at søge efter det påkrævede ord.

Ovenstående billede illustrerer følgende:

1. Du har en matrix på 10 cifre, og elementet 59 skal findes.
2. Alle elementer er markeret med indekset fra 0 – 9. Nu beregnes midten af ​​arrayet. For at gøre det tager du indeksets værdier længst til venstre og højre og dividerer dem med 2. Resultatet er 4.5, men vi tager bundværdien. Derfor er midten 4.
3. Algoritmen dropper alle elementer fra midten (4) til den laveste grænse, fordi 59 er større end 24, og nu er arrayet kun tilbage med 5 elementer.
4. 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.
5. På dette tidspunkt ved du, at 59 kommer efter 45. Derfor bliver venstre indeks, som er 5, også midten.
6. Disse iterationer fortsætter, indtil arrayet er reduceret til kun ét element, eller det element, der skal findes, bliver midten af ​​arrayet.

Eksempel 2

Lad os se på følgende eksempel for at forstå, at den binære søgning fungerer

1. Du har en række sorterede værdier fra 2 til 20 og skal finde 18.
2. Gennemsnittet af de nedre og øvre grænser er (l + r) / 2 = 4. Den værdi, der søges efter, er større end midten, som er 4.
3. Arrayværdier mindre end midten udelades fra søgning, og værdier større end midtværdien 4 søges efter.
4. Dette er en tilbagevendende opdelingsproces, indtil det faktiske emne, der skal søges, er fundet.

Hvorfor har vi brug for binær søgning?

Følgende grunde gør den binære søgning til et bedre valg til at blive brugt som en 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 gennemgå dataene i en sekvens, får den binære algoritme tilfældigt adgang til dataene for at finde det nødvendige element. Dette gør søgecyklusserne kortere og mere nøjagtige.
• Binær søgning udfører sammenligninger af de sorterede data baseret på et ordensprincip end ved brug af lighedssammenligninger, som er langsommere og for det meste unøjagtige.
• Efter hver søgningscyklus deler algoritmen størrelsen af ​​arrayet i halvdelen, og i næste iteration vil den kun fungere i den resterende halvdel af arrayet

Lær vores næste tutorial af Lineær søgning: Python, C++ Eksempel

Resumé

• Søg er et værktøj, 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 elementer.
• Binær søgning er almindeligvis kendt som en halvintervalsøgning eller en logaritmisk søgning
• Det virker ved at dele arrayet i halvdelen ved hver iteration under det påkrævede element, der er fundet.
• binær algoritme tager midten af ​​arrayet ved at dividere summen af ​​indeksværdierne til venstre og længst til højre med 2. Nu falder algoritmen enten den nedre eller øvre grænse af elementer fra midten af ​​arrayet, afhængigt af det element, der skal findes.
• Algoritmen får tilfældigt adgang til dataene for at finde det nødvendige element. Dette gør søgecyklusserne kortere og mere nøjagtige.
• Binær søgning udfører sammenligninger af de sorterede data baseret på et ordensprincip end at bruge lighedssammenligninger, der er langsomme og unøjagtige.
• En binær søgning er ikke egnet til usorterede data.