TechCodeview

Deze tutorial leert hoe we een binair zoekalgoritme kunnen toepassen met behulp van Python om de indexpositie van een element in de gegeven lijst te vinden.

Invoering

Een binaire zoekopdracht is een algoritme om een ​​bepaald element in de lijst te vinden. Stel dat we een lijst met duizend elementen hebben en dat we een indexpositie van een bepaald element nodig hebben. We kunnen de indexpositie van het element zeer snel vinden met behulp van het binaire zoekalgoritme.

Er zijn veel zoekalgoritmen, maar de binaire zoekopdracht is het populairst.

De elementen in de lijst moeten worden gesorteerd om het binaire zoekalgoritme toe te passen. Als elementen niet gesorteerd zijn, sorteer ze dan eerst.

Laten we het concept van binair zoeken begrijpen.

Concept van binair zoeken

In het binaire zoekalgoritme kunnen we de elementpositie vinden met behulp van de volgende methoden.

• Recursieve methode
• Iteratieve methode

De verdeel-en-heers-aanpaktechniek wordt gevolgd door de recursieve methode. Bij deze methode wordt een functie steeds opnieuw aangeroepen totdat deze een element in de lijst heeft gevonden.

Een reeks instructies wordt meerdere keren herhaald om de indexpositie van een element in de iteratieve methode te vinden. De terwijl lus wordt gebruikt om deze taak te volbrengen.

Binair zoeken is effectiever dan lineair zoeken, omdat we niet in elke lijstindex hoeven te zoeken. De lijst moet worden gesorteerd om het binaire zoekalgoritme te bereiken.

Laten we een stapsgewijze implementatie van binair zoeken uitvoeren.

We hebben een gesorteerde lijst met elementen en we zoeken naar de indexpositie van 45.

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

We plaatsen dus twee aanwijzingen in onze lijst. Eén aanwijzer wordt gebruikt om de kleinere aangeroepen waarde aan te duiden laag en de tweede aanwijzer wordt gebruikt om de hoogste opgeroepen waarde aan te duiden hoog .

Vervolgens berekenen we de waarde van de midden element in de array.

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

Nu vergelijken we het gezochte element met de middelste indexwaarde. In dit geval, 32 is niet gelijk aan Vier vijf. We moeten dus verdere vergelijkingen uitvoeren om het element te vinden.

Als het getal dat we zoeken gelijk is aan het midden. Keer dan terug midden ga anders verder met de vergelijking.

Het te zoeken getal is groter dan het midden nummer, we vergelijken de N met het middelste element van de elementen aan de rechterkant van midden en laag ingesteld op laag = midden + 1.

Vergelijk anders de N met de middelste element van de elementen aan de linkerkant van midden En instellen hoog naar hoog = midden - 1.

Herhaal dit totdat het nummer dat we zoeken is gevonden.

Implementeer een binaire zoekopdracht in Python

Eerst implementeren we een binaire zoekopdracht met de iteratieve methode. We zullen een reeks uitspraken herhalen en elk item van de lijst herhalen. We zullen de middelste waarde vinden totdat de zoekopdracht is voltooid.

Laten we het volgende programma van de iteratieve methode begrijpen.

Python-implementatie

 # 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></=>

Uitleg:

In het bovenstaande programma -

• We hebben een functie gemaakt met de naam Binaire zoekopdracht() functie waaraan twee argumenten moeten doorgegeven worden: een lijst die moet worden gesorteerd en een getal dat moet worden doorzocht.
• We hebben twee variabelen gedeclareerd om de laagste en hoogste waarden in de lijst op te slaan. De laagste waarde krijgt een initiële waarde van 0, hoog naar len(lijst1) - 1 en midden als 0.
• Vervolgens hebben we de terwijl lus met de voorwaarde dat de laagste is gelijk en kleiner dan de hoogste De while-lus herhaalt zich als het nummer nog niet is gevonden.
• In de while-lus vinden we de middenwaarde en vergelijken we de indexwaarde met het getal waarnaar we zoeken.
• Als de waarde van de middenindex kleiner is dan N , verhogen we de middenwaarde met 1 en wijzen deze toe aan De zoekopdracht gaat naar de linkerkant.
• Anders verlaagt u de middenwaarde en wijst u deze toe aan de hoog . De zoekopdracht verplaatst zich naar de rechterkant.
• Als de n gelijk is aan de middelste waarde, keer dan terug midden .
• Dit zal gebeuren tot en met laag is gelijk en kleiner dan de hoog .
• Als we het einde van de functie bereiken, is het element niet aanwezig in de lijst. We retourneren -1 naar de aanroepende functie.

Laten we de recursieve methode van binair zoeken begrijpen.

Recursief binair zoeken

De recursiemethode kan worden gebruikt bij binair zoeken. Hierin zullen we een recursieve functie definiëren die zichzelf blijft aanroepen totdat deze aan de voorwaarde voldoet.

Laten we het bovenstaande programma begrijpen met behulp van de recursieve functie.

Python-programma

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

Uitgang:

 Element is present at index 2 

Uitleg

een csv-bestand lezen in Java

Het bovenstaande programma is vergelijkbaar met het vorige programma. We hebben een recursieve functie en de basisvoorwaarde gedeclareerd. Voorwaarde is dat de laagste waarde kleiner is dan of gelijk is aan de hoogste waarde.

• We berekenen het middelste getal zoals in het laatste programma.
• Wij hebben gebruik gemaakt van de als instructie om door te gaan met de binaire zoekopdracht.
• Als de middelste waarde gelijk is aan het getal waarnaar we op zoek zijn, wordt de middelste waarde geretourneerd.
• Als de middelste waarde kleiner is dan de waarde, kijken we naar onze recursieve functie Binaire zoekopdracht() nogmaals en verhoog de middenwaarde met één en wijs deze toe aan laag.
• Als de middelste waarde groter is dan de waarde waarnaar we kijken, dan is onze recursieve functie Binaire zoekopdracht() nogmaals en verlaag de middenwaarde met één en wijs deze toe aan laag.

In het laatste deel hebben we ons hoofdprogramma geschreven. Het is hetzelfde als het vorige programma, maar het enige verschil is dat we twee parameters hebben doorgegeven in het Binaire zoekopdracht() functie.

Dit komt omdat we de initiële waarden niet kunnen toewijzen aan laag, hoog en midden in de recursieve functie. Elke keer dat de recursieve wordt aangeroepen, wordt de waarde voor die variabelen opnieuw ingesteld. Dat zal een verkeerd resultaat opleveren.

Complexiteit

De complexiteit van het binaire zoekalgoritme is O(1) voor het beste geval. Dit gebeurt als het element dat we zoeken in de eerste vergelijking wordt gevonden. De O(login) is de slechtste en de gemiddelde complexiteit van de binaire zoekopdracht. Dit is afhankelijk van het aantal zoekopdrachten dat wordt uitgevoerd om het element te vinden waarnaar we op zoek zijn.

Conclusie

Een binair zoekalgoritme is de meest efficiënte en snelle manier om een ​​element in de lijst te doorzoeken. Het slaat de onnodige vergelijking over. Zoals de naam al doet vermoeden, bestaat de zoektocht uit twee delen. Het concentreert zich op de kant van de lijst, die dicht bij het nummer ligt waarnaar we zoeken.

We hebben beide methoden besproken om de indexpositie van het gegeven getal te vinden.