TechCodeview

Denne tutorial vil lære, hvordan vi kan anvende en binær søgealgoritme ved hjælp af Python til at finde et elements indeksposition på den givne liste.

Introduktion

En binær søgning er en algoritme til at finde et bestemt element på listen. Antag, at vi har en liste med tusinde elementer, og vi skal have en indeksposition for et bestemt element. Vi kan finde elementets indeksposition meget hurtigt ved hjælp af den binære søgealgoritme.

Der er mange søgealgoritmer, men den binære søgning er mest populær blandt dem.

Elementerne i listen skal sorteres for at anvende den binære søgealgoritme. Hvis elementer ikke er sorteret, så sorter dem først.

Lad os forstå begrebet binær søgning.

Begrebet binær søgning

I den binære søgealgoritme kan vi finde elementets position ved hjælp af følgende metoder.

liste som array

• Rekursiv metode
• Iterativ metode

Del og hersk tilgangsteknikken følges af den rekursive metode. I denne metode kaldes en funktion sig selv igen og igen, indtil den fandt et element i listen.

Et sæt udsagn gentages flere gange for at finde et elements indeksposition i den iterative metode. Det mens loop bruges til at udføre denne opgave.

Binær søgning er mere effektiv end den lineære søgning, fordi vi ikke behøver at søge i hvert listeindeks. Listen skal sorteres for at opnå den binære søgealgoritme.

Lad os få en trinvis implementering af binær søgning.

Vi har en sorteret liste over elementer, og vi leder efter indekspositionen på 45.

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

Så vi sætter to pointer på vores liste. En pointer bruges til at angive den mindre værdi kaldet lav og den anden pointer bruges til at angive den højeste værdi, der kaldes høj .

java array dynamisk

Dernæst beregner vi værdien af midten element i arrayet.

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

Nu vil vi sammenligne det søgte element med den midterste indeksværdi. I dette tilfælde, 32 er ikke lig med Fire. Fem. Så vi er nødt til at foretage yderligere sammenligning for at finde elementet.

Hvis tallet, vi søger, er lig med midten. Så vend tilbage midt ellers gå videre til den videre sammenligning.

Antallet, der skal søges, er større end midten antal, sammenligner vi n med elementernes midterste element på højre side af midt og sæt lav til lav = mellem + 1.

Ellers sammenligne n med midterste element af elementerne på venstre side af midt og sæt høj til høj = midt - 1.

for hver maskinskrift

Gentag indtil det nummer, vi søger efter, er fundet.

Implementer en binær søgning i Python

Først implementerer vi en binær søgning med den iterative metode. Vi gentager et sæt udsagn og gentager hvert punkt på listen. Vi finder den midterste værdi, indtil søgningen er færdig.

Lad os forstå følgende program for den iterative metode.

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 ovenstående program -

• Vi har lavet en funktion kaldet binær_søgning() funktion som tager to argumenter - en liste der skal sorteres og et tal der skal søges i.
• Vi har erklæret to variable for at gemme de laveste og højeste værdier på listen. Den lave tildeles startværdien til 0, høj til len(liste1) - 1 og midt som 0.
• Dernæst har vi erklæret mens sløjfe med den betingelse, at den laveste er lig og mindre end højest While-løkken vil iterere, hvis nummeret ikke er fundet endnu.
• I while-løkken finder vi midtværdien og sammenligner indeksværdien med det tal, vi søger efter.
• Hvis værdien af ​​midtindekset er mindre end n , øger vi mellemværdien med 1 og tildeler den til Søgningen flytter til venstre side.
• Ellers skal du reducere mellemværdien og tildele den til høj . Søgningen flytter til højre side.
• Hvis n er lig med middelværdien, så vend tilbage midt .
• Dette vil ske indtil d lav er lig og mindre end høj .
• Hvis vi når til slutningen af ​​funktionen, er elementet ikke til stede i listen. Vi returnerer -1 til den kaldende funktion.

Lad os forstå den rekursive metode til binær søgning.

Rekursiv binær søgning

Rekursionsmetoden kan bruges i den binære søgning. I dette vil vi definere en rekursiv funktion, der bliver ved med at kalde sig selv, indtil den opfylder betingelsen.

Lad os forstå ovenstående program ved hjælp af den rekursive funktion.

Python program

 # 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') 

Produktion:

 Element is present at index 2 

Forklaring

Ovenstående program ligner det tidligere program. Vi erklærede en rekursiv funktion og dens basistilstand. Betingelsen er, at den laveste værdi er mindre eller lig med den højeste værdi.

• Vi beregner det midterste tal som i sidste program.
• Vi har brugt hvis sætning for at fortsætte med den binære søgning.
• Hvis den midterste værdi er lig med det tal, vi leder efter, returneres den midterste værdi.
• Hvis den midterste værdi er mindre end værdien, søger vi derefter vores rekursive funktion binær_søgning() igen og øg mellemværdien med én og tildel til lav.
• Hvis den midterste værdi er større end den værdi, vi leder efter, er vores rekursive funktion binær_søgning() igen og sænk mellemværdien med én og tildel den til lav.

I sidste del har vi skrevet vores hovedprogram. Det er det samme som det forrige program, men den eneste forskel er, at vi har bestået to parametre i binær_søgning() fungere.

Dette skyldes, at vi ikke kan tildele startværdierne til lav, høj og mellem i den rekursive funktion. Hver gang det rekursive kaldes vil værdien blive nulstillet for disse variable. Det vil give det forkerte resultat.

Kompleksitet

Kompleksiteten af ​​den binære søgealgoritme er O(1) i bedste fald. Dette sker, hvis det element, det element, vi søger, finder i den første sammenligning. Det O(logn) er den værste og den gennemsnitlige sagskompleksitet af den binære søgning. Dette afhænger af antallet af søgninger, der udføres for at finde det element, vi leder efter.

java omrøring til int

Konklusion

En binær søgealgoritme er den mest effektive og hurtige måde at søge efter et element på listen. Det springer den unødvendige sammenligning over. Som navnet antyder, er søgningen opdelt i to dele. Den fokuserer på siden af ​​listen, som er tæt på det tal, vi søger.

Vi har diskuteret begge metoder til at finde indekspositionen for det givne tal.