TechCodeview

Tämä opetusohjelma oppii kuinka voimme soveltaa binaarihakualgoritmia Pythonilla löytääksemme elementin indeksipaikan annetusta luettelosta.

Johdanto

Binäärihaku on algoritmi tietyn elementin löytämiseksi luettelosta. Oletetaan, että meillä on luettelo tuhannesta elementistä ja meidän on saatava tietyn elementin indeksipaikka. Löydämme elementin indeksipaikan erittäin nopeasti käyttämällä binaarihakualgoritmia.

Hakualgoritmeja on monia, mutta binäärihaku on niistä suosituin.

Listan elementit on lajiteltava binäärihakualgoritmin soveltamiseksi. Jos elementtejä ei ole lajiteltu, lajittele ne ensin.

Ymmärretään binäärihaun käsite.

Binäärihaun käsite

Binäärihakualgoritmissa voimme löytää elementin sijainnin seuraavilla menetelmillä.

listasolmu

• Rekursiivinen menetelmä
• Iteratiivinen menetelmä

Jaa ja hallitse -lähestymistapatekniikkaa seuraa rekursiivinen menetelmä. Tässä menetelmässä funktiota kutsutaan itseään uudestaan ​​ja uudestaan, kunnes se löytää elementin luettelosta.

Joukko lauseita toistetaan useita kertoja elementin indeksipaikan löytämiseksi iteratiivisessa menetelmässä. The sillä aikaa silmukkaa käytetään tämän tehtävän suorittamiseen.

Binäärihaku on tehokkaampi kuin lineaarinen haku, koska meidän ei tarvitse etsiä jokaisesta luettelohakemistosta. Lista on lajiteltava binäärihakualgoritmin saavuttamiseksi.

Otetaan vaiheittainen binaarihaun toteutus.

Meillä on lajiteltu luettelo elementeistä, ja etsimme indeksin sijaintia 45.

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

Joten asetamme luetteloomme kaksi osoitinta. Yhtä osoitinta käytetään osoittamaan pienempi arvo, jota kutsutaan matala ja toista osoitinta käytetään osoittamaan suurinta arvoa korkea .

Seuraavaksi laskemme arvon keskellä elementti taulukossa.

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

Nyt verrataan haettua elementtiä indeksin keskiarvoon. Tässä tapauksessa, 32 ei ole yhtä suuri kuin Neljä viisi. Joten meidän on tehtävä lisävertailua elementin löytämiseksi.

Jos etsimämme numero on yhtä suuri kuin keskiarvo. Palaa sitten takaisin mid muussa tapauksessa siirry myöhempään vertailuun.

Haettava numero on suurempi kuin keskellä numero, vertaamme n elementtien keskielementti on oikealla puolella mid ja aseta matalaksi alhainen = keski + 1.

Muussa tapauksessa vertaa n kanssa keskimmäinen elementti vasemmalla puolella olevista elementeistä mid ja aseta korkea kohtaan korkea = keski - 1.

Toista, kunnes etsimämme numero löytyy.

Toteuta binaarihaku Pythonissa

Ensin toteutamme binaarihaun iteratiivisella menetelmällä. Toistamme joukon lauseita ja toistamme jokaisen luettelon kohdan. Etsimme keskiarvon, kunnes haku on valmis.

Ymmärretään seuraava iteratiivisen menetelmän ohjelma.

Python-toteutus

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

Selitys:

Yllä olevassa ohjelmassa -

• Olemme luoneet funktion nimeltä binary_search() funktio, joka ottaa kaksi argumenttia - lajiteltavan luettelon ja haun luvun.
• Olemme ilmoittaneet kaksi muuttujaa tallentamaan luettelon pienimmän ja suurimman arvon. Alimmalle asetetaan alkuarvo 0, korkea kohtaan len(lista1) - 1 ja keskiarvo 0.
• Seuraavaksi olemme julistaneet sillä aikaa silmukan sillä ehdolla, että alhaisin on yhtä suuri ja pienempi kuin korkein While-silmukka toistuu, jos numeroa ei ole vielä löydetty.
• While-silmukassa löydämme keskiarvon ja vertaamme indeksin arvoa etsimään numeroon.
• Jos keskiindeksin arvo on pienempi kuin n , lisäämme keskiarvoa 1:llä ja määritämme sen Haku siirtyy vasemmalle puolelle.
• Muussa tapauksessa vähennä keskiarvoa ja määritä se korkea . Haku siirtyy oikealle puolelle.
• Jos n on yhtä suuri kuin keskiarvo, palaa mid .
• Tämä tapahtuu kunnes matala on yhtä suuri ja pienempi kuin korkea .
• Jos saavutamme funktion lopussa, elementtiä ei ole luettelossa. Palaamme -1 kutsuvaan funktioon.

Ymmärretään binäärihaun rekursiivinen menetelmä.

Rekursiivinen binaarihaku

Binäärihaussa voidaan käyttää rekursiomenetelmää. Tässä määrittelemme rekursiivisen funktion, joka kutsuu itseään, kunnes se täyttää ehdon.

tostring menetelmä

Ymmärretään yllä oleva ohjelma rekursiivisen funktion avulla.

Python ohjelma

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

Lähtö:

 Element is present at index 2 

Selitys

Yllä oleva ohjelma on samanlainen kuin edellinen ohjelma. Ilmoitimme rekursiivisen funktion ja sen perusehdon. Ehto on, että pienin arvo on pienempi tai yhtä suuri kuin suurin arvo.

• Laskemme keskiluvun kuten edellisessä ohjelmassa.
• Olemme käyttäneet jos lauseke jatkaaksesi binaarihakua.
• Jos keskimmäinen arvo on yhtä suuri kuin etsimme, keskimmäinen arvo palautetaan.
• Jos keskiarvo on pienempi kuin arvo, katsomme sitten rekursiivista funktiota binary_search() uudelleen ja lisää keskiarvoa yhdellä ja määritä matalaksi.
• Jos keskiarvo on suurempi kuin arvo, jota etsimme, rekursiivinen funktiomme binary_search() uudelleen ja pienennä keskiarvoa yhdellä ja määritä se matalaksi.

Viimeisessä osassa olemme kirjoittaneet pääohjelmamme. Se on sama kuin edellinen ohjelma, mutta ainoa ero on, että olemme läpäisseet kaksi parametria binary_search() toiminto.

Tämä johtuu siitä, että emme voi määrittää alkuarvoja rekursiivisen funktion arvoille alhainen, korkea ja keskiarvo. Aina kun rekursiivia kutsutaan, arvo nollataan näille muuttujille. Se antaa väärän tuloksen.

Monimutkaisuus

Binäärihakualgoritmin monimutkaisuus on O(1) parhaassa tapauksessa. Tämä tapahtuu, jos etsimämme elementti löytyy ensimmäisestä vertailusta. The O (kirjaudu sisään) on binäärihaun huonoin ja keskimääräinen tapaus. Tämä riippuu siitä, kuinka monta hakua etsimme elementin löytämiseksi tehdään.

Johtopäätös

Binäärihakualgoritmi on tehokkain ja nopein tapa etsiä elementtiä luettelosta. Se ohittaa turhan vertailun. Kuten nimestä voi päätellä, haku on jaettu kahteen osaan. Se keskittyy luettelon puolelle, joka on lähellä etsimäämme numeroa.

Olemme keskustelleet molemmista menetelmistä tietyn luvun indeksipaikan löytämiseksi.