Denne opplæringen vil lære hvordan vi kan bruke en binær søkealgoritme ved å bruke Python for å finne et elements indeksposisjon i den gitte listen.

Introduksjon

Et binært søk er en algoritme for å finne et bestemt element i listen. Anta at vi har en liste over tusen elementer, og vi må få en indeksposisjon for et bestemt element. Vi kan finne elementets indeksposisjon veldig raskt ved å bruke den binære søkealgoritmen.

Det er mange søkealgoritmer, men det binære søket er mest populært blant dem.

Elementene i listen må sorteres for å bruke den binære søkealgoritmen. Hvis elementene ikke er sortert, sorter dem først.

La oss forstå konseptet med binært søk.

Konseptet med binært søk

I den binære søkealgoritmen kan vi finne elementposisjonen ved å bruke følgende metoder.

liste som array

• Rekursiv metode
• Iterativ metode

Skille og hersk tilnærmingsteknikken følges av den rekursive metoden. I denne metoden kalles en funksjon seg selv igjen og igjen til den fant et element i listen.

Et sett med utsagn gjentas flere ganger for å finne et elements indeksposisjon i den iterative metoden. De samtidig som loop brukes for å utføre denne oppgaven.

Binært søk er mer effektivt enn lineært søk fordi vi ikke trenger å søke i hver listeindeks. Listen må sorteres for å oppnå den binære søkealgoritmen.

La oss ha en trinnvis implementering av binært søk.

Vi har en sortert liste over elementer, og vi ser etter indeksposisjonen 45.

[12, 24, 32, 39, 45, 50, 54]

Så vi setter to pekere i listen vår. En peker brukes til å angi den minste verdien som kalles lav og den andre pekeren brukes til å angi den høyeste verdien som kalles høy .

java array dynamisk

Deretter beregner vi verdien av midten element i matrisen.

 mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer) 

Nå vil vi sammenligne det søkte elementet med midtindeksverdien. I dette tilfellet, 32 er ikke lik Fire fem. Så vi må gjøre ytterligere sammenligning for å finne elementet.

Hvis tallet vi søker lik midten. Gå deretter tilbake midten ellers gå til den videre sammenligningen.

Antallet som skal søkes er større enn midten antall, sammenligner vi n med midtelementet til elementene på høyre side av midten og sett lavt til lav = middels + 1.

Ellers, sammenlign n med midtelement av elementene på venstre side av midten og sett høy til høy = midt - 1.

for hver maskinskrift

Gjenta til nummeret vi søker etter er funnet.

Implementer et binært søk i Python

Først implementerer vi et binært søk med den iterative metoden. Vi vil gjenta et sett med utsagn og gjenta hvert punkt på listen. Vi finner den midterste verdien til søket er fullført.

La oss forstå følgende program for den iterative metoden.

Python-implementering

 # Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let&apos;s understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let&apos;s understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;) </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can&apos;t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=>

Forklaring:

I programmet ovenfor -

• Vi har laget en funksjon som heter binært_søk() funksjon som tar to argumenter - en liste som skal sorteres og et tall som skal søkes.
• Vi har erklært to variabler for å lagre de laveste og høyeste verdiene i listen. Den lave tildeles startverdien til 0, høy til len(liste1) - 1 og midt som 0.
• Deretter har vi erklært samtidig som sløyfe med betingelsen om at lavest er lik og mindre enn høyest While-løkken vil iterere hvis nummeret ikke er funnet ennå.
• I while-løkken finner vi midtverdien og sammenligner indeksverdien med tallet vi søker etter.
• Hvis verdien av midtindeksen er mindre enn n , øker vi midtverdien med 1 og tilordner den til Søket flyttes til venstre side.
• Ellers reduserer du midtverdien og tilordner den til høy . Søket beveger seg til høyre side.
• Hvis n er lik midtverdien, så gå tilbake midten .
• Dette vil skje frem til lav er lik og mindre enn høy .
• Hvis vi kommer til slutten av funksjonen, er ikke elementet til stede i listen. Vi returnerer -1 til kallefunksjonen.

La oss forstå den rekursive metoden for binært søk.

Rekursivt binært søk

Rekursjonsmetoden kan brukes i det binære søket. I dette vil vi definere en rekursiv funksjon som fortsetter å kalle seg selv til den oppfyller betingelsen.

La oss forstå programmet ovenfor ved å bruke den rekursive funksjonen.

Python-programmet

 # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print('Element is present at index', str(res)) else: print('Element is not present in list1') 

Produksjon:

 Element is present at index 2 

Forklaring

Programmet ovenfor ligner det forrige programmet. Vi erklærte en rekursiv funksjon og dens basistilstand. Betingelsen er at den laveste verdien er mindre eller lik den høyeste verdien.

• Vi beregner midttallet som i forrige program.
• Vi har brukt hvis setning for å fortsette med det binære søket.
• Hvis den midterste verdien er lik tallet vi ser etter, returneres den midterste verdien.
• Hvis den midterste verdien er mindre enn verdien, ser vi etter vår rekursive funksjon binært_søk() igjen og øk midtverdien med én og tilordne til lav.
• Hvis den midterste verdien er større enn verdien vi ser på, er vår rekursive funksjon binært_søk() igjen og reduser midtverdien med én og tilordne den til lav.

I siste del har vi skrevet hovedprogrammet vårt. Det er det samme som det forrige programmet, men den eneste forskjellen er at vi har passert to parametere i binært_søk() funksjon.

Dette er fordi vi ikke kan tilordne startverdiene til lav, høy og middels i den rekursive funksjonen. Hver gang det rekursive kalles, vil verdien bli tilbakestilt for disse variablene. Det vil gi feil resultat.

Kompleksitet

Kompleksiteten til den binære søkealgoritmen er O(1) i beste fall. Dette skjer hvis elementet som elementet vi ser finner i den første sammenligningen. De O(logn) er den verste og gjennomsnittlige sakskompleksiteten til det binære søket. Dette avhenger av antall søk som utføres for å finne elementet vi leter etter.

ressursallokeringsgraf

Konklusjon

En binær søkealgoritme er den mest effektive og raske måten å søke etter et element i listen. Den hopper over den unødvendige sammenligningen. Som navnet tilsier, er søket delt i to deler. Den fokuserer på siden av listen, som er nær tallet vi søker etter.

Vi har diskutert begge metodene for å finne indeksposisjonen til det gitte tallet.