TechCodeview

Den här handledningen kommer att lära oss hur vi kan tillämpa en binär sökalgoritm med Python för att hitta ett elements indexposition i den givna listan.

Introduktion

En binär sökning är en algoritm för att hitta ett visst element i listan. Anta att vi har en lista med tusen element, och vi behöver få en indexposition för ett visst element. Vi kan hitta elementets indexposition mycket snabbt med den binära sökalgoritmen.

Det finns många sökalgoritmer men den binära sökningen är mest populär bland dem.

Elementen i listan måste sorteras för att tillämpa den binära sökalgoritmen. Om element inte är sorterade, sortera dem först.

Låt oss förstå konceptet med binär sökning.

Begreppet binär sökning

I den binära sökalgoritmen kan vi hitta elementets position med hjälp av följande metoder.

• Rekursiv metod
• Iterativ metod

Tekniken dividera och härska följs av den rekursiva metoden. I denna metod kallas en funktion om och om igen tills den hittat ett element i listan.

En uppsättning satser upprepas flera gånger för att hitta ett elements indexposition i den iterativa metoden. De medan loop används för att utföra denna uppgift.

Binär sökning är mer effektiv än linjär sökning eftersom vi inte behöver söka i varje listindex. Listan måste sorteras för att uppnå den binära sökalgoritmen.

Låt oss ha en steg för steg implementering av binär sökning.

Vi har en sorterad lista med element, och vi letar efter indexpositionen 45.

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

Så vi sätter två pekare i vår lista. En pekare används för att beteckna det mindre värdet som kallas låg och den andra pekaren används för att beteckna det högsta anropade värdet hög .

Därefter beräknar vi värdet på mitten element i arrayen.

hur man läser en json-fil

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

Nu kommer vi att jämföra det sökta elementet med mittindexvärdet. I detta fall, 32 är inte lika med Fyra fem. Så vi måste göra ytterligare jämförelse för att hitta elementet.

Om talet vi söker är lika med mitten. Återvänd sedan mitten gå annars till den ytterligare jämförelsen.

Antalet som ska sökas är större än mitten antal, jämför vi n med elementens mittelement på höger sida av mitten och sätt lågt till låg = mitten + 1.

Annars, jämför n med mittelement av elementen på vänster sida av mitten och ställ in hög till hög = mitten - 1.

Upprepa tills numret som vi söker efter hittas.

Implementera en binär sökning i Python

Först implementerar vi en binär sökning med den iterativa metoden. Vi kommer att upprepa en uppsättning påståenden och upprepa varje punkt i listan. Vi hittar mittvärdet tills sökningen är klar.

Låt oss förstå följande program för den iterativa 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></=>

Förklaring:

I programmet ovan -

• Vi har skapat en funktion som heter binary_search() funktion som tar två argument - en lista som ska sorteras och ett nummer som ska sökas.
• Vi har deklarerat två variabler för att lagra de lägsta och högsta värdena i listan. Det låga tilldelas initialt värde till 0, hög till len(lista1) - 1 och mitten som 0.
• Därefter har vi deklarerat medan slinga med villkoret att lägst är lika och mindre än högsta While-slingan kommer att upprepas om numret inte har hittats ännu.
• I while-loopen hittar vi mittvärdet och jämför indexvärdet med talet vi söker efter.
• Om värdet på mittindexet är mindre än n , ökar vi mittvärdet med 1 och tilldelar det till Sökningen flyttas till vänster sida.
• Annars minskar du mittvärdet och tilldelar det till hög . Sökningen flyttas till höger sida.
• Om n är lika med mittvärdet, gå tillbaka mitten .
• Detta kommer att hända tills låg är lika och mindre än hög .
• Om vi ​​når slutet av funktionen, så finns inte elementet i listan. Vi returnerar -1 till den anropande funktionen.

Låt oss förstå den rekursiva metoden för binär sökning.

Rekursiv binär sökning

Rekursionsmetoden kan användas i den binära sökningen. I detta kommer vi att definiera en rekursiv funktion som fortsätter att anropa sig själv tills den uppfyller villkoret.

Låt oss förstå programmet ovan med den rekursiva funktionen.

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

Produktion:

 Element is present at index 2 

Förklaring

Ovanstående program liknar det tidigare programmet. Vi deklarerade en rekursiv funktion och dess basvillkor. Villkoret är att det lägsta värdet är mindre eller lika med det högsta värdet.

• Vi räknar ut mitttalet som i förra programmet.
• Vi har använt om för att fortsätta med den binära sökningen.
• Om det mellersta värdet är lika med talet som vi letar efter, returneras mittvärdet.
• Om mittvärdet är mindre än värdet, tittar vi på vår rekursiva funktion binary_search() igen och öka mittvärdet med ett och tilldela till lågt.
• Om det mellersta värdet är större än värdet vi letar efter så är vår rekursiva funktion binary_search() igen och minska mittvärdet med ett och tilldela det till lågt.

I den sista delen har vi skrivit vårt huvudprogram. Det är samma som det tidigare programmet, men den enda skillnaden är att vi har passerat två parametrar i binary_search() fungera.

Detta beror på att vi inte kan tilldela de initiala värdena till låg, hög och mellan i den rekursiva funktionen. Varje gång den rekursiva anropas kommer värdet att återställas för dessa variabler. Det kommer att ge fel resultat.

Komplexitet

Komplexiteten hos den binära sökalgoritmen är O(1) i bästa fall. Detta händer om elementet som elementet vi letar efter hittar i den första jämförelsen. De O(logga) är den värsta och genomsnittliga fallkomplexiteten för den binära sökningen. Detta beror på antalet sökningar som görs för att hitta det element som vi letar efter.

Slutsats

En binär sökalgoritm är det mest effektiva och snabba sättet att söka efter ett element i listan. Den hoppar över den onödiga jämförelsen. Som namnet antyder är sökningen uppdelad i två delar. Den fokuserar på sidan av listan, som är nära numret som vi söker.

Vi har diskuterat båda metoderna för att hitta indexpositionen för det givna numret.