Šioje pamokoje sužinosite, kaip galime pritaikyti dvejetainį paieškos algoritmą naudodami Python, kad surastume elemento rodyklės padėtį pateiktame sąraše.

Įvadas

Dvejetainė paieška yra algoritmas, leidžiantis rasti tam tikrą elementą sąraše. Tarkime, kad turime tūkstančių elementų sąrašą ir turime gauti konkretaus elemento indekso poziciją. Naudodami dvejetainį paieškos algoritmą galime labai greitai rasti elemento indekso poziciją.

atsiskaitymas su git

Yra daug paieškos algoritmų, tačiau populiariausia tarp jų yra dvejetainė paieška.

Sąrašo elementai turi būti surūšiuoti, kad būtų taikomas dvejetainis paieškos algoritmas. Jei elementai nesurūšiuoti, pirmiausia juos surūšiuokite.

Supraskime dvejetainės paieškos sąvoką.

Dvejetainės paieškos samprata

Dvejetainėje paieškos algoritme elemento vietą galime rasti šiais metodais.

• Rekursyvinis metodas
• Iteracinis metodas

Skaldyk ir valdyk metodo metodą seka rekursinis metodas. Taikant šį metodą, funkcija vėl ir vėl iškviečiama pati, kol randa elementą sąraše.

Teiginių rinkinys kartojamas kelis kartus, kad būtų galima rasti elemento indekso poziciją iteraciniame metode. The kol Šiai užduočiai atlikti naudojama kilpa.

Dvejetainė paieška yra efektyvesnė nei linijinė paieška, nes nereikia ieškoti kiekvieno sąrašo indekso. Sąrašas turi būti surūšiuotas, kad būtų pasiektas dvejetainis paieškos algoritmas.

Žingsnis po žingsnio įgyvendinkime dvejetainę paiešką.

Turime surūšiuotą elementų sąrašą ir ieškome 45 indekso pozicijos.

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

Taigi, savo sąraše nustatome dvi nuorodas. Vienas žymeklis naudojamas mažesnei vadinamajai reikšmei pažymėti žemas o antroji rodyklė naudojama didžiausiai vadinamajai reikšmei žymėti aukštas .

Toliau apskaičiuojame vertę vidurio elementas masyve.

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

Dabar palyginsime ieškomą elementą su vidutine indekso reikšme. Tokiu atveju, 32 nėra lygus Keturi. Taigi, norėdami rasti elementą, turime atlikti tolesnį palyginimą.

Jei skaičius, kurio ieškome, yra lygus viduriui. Tada grįžk vidurio kitu atveju pereikite prie tolesnio palyginimo.

Skaičius, kurio reikia ieškoti, yra didesnis nei vidurio skaičių, lyginame n su viduriniu elementų elementu dešinėje pusėje vidurio ir nustatykite žemai žemas = vidutinis + 1.

Kitu atveju palyginkite n su vidurinis elementas elementų kairėje pusėje vidurio ir nustatyti aukštas į aukštas = vidutinis - 1.

Kartokite tol, kol bus rastas mūsų ieškomas numeris.

Įdiekite dvejetainę paiešką Python

Pirma, įgyvendiname dvejetainę paiešką iteraciniu metodu. Pakartosime teiginių rinkinį ir kartosime kiekvieną sąrašo elementą. Vidurinę reikšmę rasime tol, kol paieška bus baigta.

Supraskime šią iteracinio metodo programą.

Python diegimas

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

Paaiškinimas:

Aukščiau pateiktoje programoje -

• Sukūrėme funkciją, vadinamą binary_search() funkcija, kuri turi du argumentus – sąrašą, kurį reikia rūšiuoti, ir skaičių, kurio reikia ieškoti.
• Mes paskelbėme du kintamuosius, kad saugotume mažiausią ir didžiausią sąrašo reikšmes. Žemiausia vertė priskiriama 0, aukštas į len(sąrašas1) - 1 ir vidurys kaip 0.
• Toliau mes paskelbėme kol kilpa su sąlyga, kad Žemiausia yra lygus ir mažesnis už aukščiausias Ciklas while kartojasi, jei numeris dar nerastas.
• Nors cikle randame vidutinę vertę ir palyginame indekso reikšmę su ieškomu skaičiumi.
• Jei vidutinio indekso reikšmė mažesnė už n , padidiname vidutinę reikšmę 1 ir priskiriame Paieška juda į kairę pusę.
• Kitu atveju sumažinkite vidutinę vertę ir priskirkite ją aukštas . Paieška pereina į dešinę pusę.
• Jei n yra lygus vidutinei reikšmei, grąžinkite vidurio .
• Tai vyks iki žemas yra lygus ir mažesnis už aukštas .
• Jei pasiekiame funkcijos pabaigą, elemento sąraše nėra. Grąžiname -1 į iškvietimo funkciją.

Supraskime rekursinį dvejetainės paieškos metodą.

Rekursinė dvejetainė paieška

Dvejetainėje paieškoje galima naudoti rekursijos metodą. Čia mes apibrėžsime rekursinę funkciją, kuri ir toliau skambina, kol įvykdys sąlygą.

Supraskime aukščiau pateiktą programą naudodami rekursinę funkciją.

Python programa

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

Išvestis:

 Element is present at index 2 

Paaiškinimas

Aukščiau pateikta programa yra panaši į ankstesnę programą. Mes paskelbėme rekursinę funkciją ir jos bazinę sąlygą. Sąlyga yra ta, kad mažiausia vertė yra mažesnė arba lygi didžiausiai vertei.

• Vidurinį skaičių apskaičiuojame kaip ir paskutinėje programoje.
• Mes panaudojome jeigu pareiškimas tęsti dvejetainę paiešką.
• Jei vidutinė reikšmė lygi skaičiui, kurio ieškome, grąžinama vidurinė reikšmė.
• Jei vidutinė reikšmė yra mažesnė už reikšmę, mes žiūrime į mūsų rekursinę funkciją binary_search() dar kartą ir padidinkite vidutinę vertę vienu ir priskirkite žemai.
• Jei vidutinė reikšmė yra didesnė už reikšmę, kurią ieškome, tada mūsų rekursinė funkcija binary_search() vėl ir sumažinkite vidutinę vertę vienu ir priskirkite ją žemai.

Paskutinėje dalyje parašėme savo pagrindinę programą. Tai tokia pati kaip ir ankstesnė programa, tačiau vienintelis skirtumas yra tas, kad mes perdavėme du parametrus binary_search() funkcija.

Taip yra todėl, kad rekursinėje funkcijoje negalime priskirti pradinių reikšmių žemai, aukštai ir vidutinei. Kiekvieną kartą, kai iškviečiamas rekursyvas, tų kintamųjų reikšmė bus nustatyta iš naujo. Tai duos neteisingą rezultatą.

Sudėtingumas

Dvejetainės paieškos algoritmo sudėtingumas yra O(1) geriausiu atveju. Taip atsitinka, jei elementas, kurio ieškome, randamas pirmame palyginime. The O (prisijungti) yra blogiausias ir vidutinis dvejetainės paieškos sudėtingumo atvejis. Tai priklauso nuo paieškų, atliekamų siekiant rasti elementą, kurio ieškome, skaičiaus.

Išvada

Dvejetainis paieškos algoritmas yra efektyviausias ir greičiausias būdas ieškoti elemento sąraše. Tai praleidžia nereikalingą palyginimą. Kaip rodo pavadinimas, paieška yra padalinta į dvi dalis. Jame dėmesys sutelkiamas į sąrašo pusę, kuri yra artima mūsų ieškomam skaičiui.

Aptarėme abu būdus, kaip rasti nurodyto skaičiaus indekso poziciją.