TechCodeview

Šī apmācība uzzinās, kā mēs varam izmantot bināro meklēšanas algoritmu, izmantojot Python, lai atrastu elementa indeksa pozīciju dotajā sarakstā.

Ievads

Binārā meklēšana ir algoritms konkrēta elementa atrašanai sarakstā. Pieņemsim, ka mums ir tūkstoš elementu saraksts, un mums ir jāiegūst noteikta elementa indeksa pozīcija. Izmantojot bināro meklēšanas algoritmu, mēs varam ļoti ātri atrast elementa indeksa pozīciju.

Ir daudz meklēšanas algoritmu, bet binārā meklēšana ir vispopulārākā starp tiem.

Elementi sarakstā ir jāsakārto, lai lietotu bināro meklēšanas algoritmu. Ja elementi nav sakārtoti, vispirms sakārtojiet tos.

Izpratīsim binārās meklēšanas jēdzienu.

Binārās meklēšanas jēdziens

Binārajā meklēšanas algoritmā elementa pozīciju varam atrast, izmantojot šādas metodes.

• Rekursīvā metode
• Iteratīvā metode

Skaldi un valdi pieejas tehnikai seko rekursīvā metode. Izmantojot šo metodi, funkcija pati par sevi tiek izsaukta atkal un atkal, līdz tā atrod kādu elementu sarakstā.

masīvu sarakstu kārtošana

Paziņojumu kopa tiek atkārtota vairākas reizes, lai iteratīvajā metodē atrastu elementa indeksa pozīciju. The kamēr cilpa tiek izmantota šī uzdevuma veikšanai.

Binārā meklēšana ir efektīvāka par lineāro meklēšanu, jo mums nav jāmeklē katrā saraksta indeksā. Saraksts ir jāsakārto, lai sasniegtu bināro meklēšanas algoritmu.

Apskatīsim soli pa solim binārās meklēšanas ieviešanu.

Mums ir sakārtots elementu saraksts, un mēs meklējam indeksa pozīciju 45.

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

Tātad, mēs savā sarakstā iestatām divus rādītājus. Viens rādītājs tiek izmantots, lai apzīmētu mazāko izsaukto vērtību zems un otro rādītāju izmanto, lai apzīmētu augstāko izsaukto vērtību augsts .

Tālāk mēs aprēķinām vērtību vidū elements masīvā.

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

Tagad mēs salīdzināsim meklēto elementu ar vidējo indeksa vērtību. Šajā gadījumā, 32 nav vienāds ar Četri. Tāpēc mums ir jāveic papildu salīdzinājums, lai atrastu elementu.

Ja mūsu meklētais skaitlis ir vienāds ar vidējo. Pēc tam atgriezieties vidus pretējā gadījumā pārejiet uz tālāku salīdzināšanu.

Meklējamais skaitlis ir lielāks par vidū numuru, mēs salīdzinām n ar elementu vidējo elementu labajā pusē vidus un iestatīt zemu uz zems = vidējais + 1.

Pretējā gadījumā salīdziniet n Ar vidējais elements no elementiem kreisajā pusē vidus un iestatīt augsts uz augsts = vidējais - 1.

Atkārtojiet, līdz tiek atrasts meklētais numurs.

Ieviesiet bināro meklēšanu programmā Python

Pirmkārt, mēs ieviešam bināro meklēšanu ar iteratīvo metodi. Mēs atkārtosim paziņojumu kopu un atkārtosim katru saraksta vienumu. Mēs atradīsim vidējo vērtību, līdz meklēšana būs pabeigta.

Sapratīsim šādu iteratīvās metodes programmu.

Python ieviešana

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

Paskaidrojums:

Iepriekš minētajā programmā -

• Mēs esam izveidojuši funkciju ar nosaukumu binary_search() funkcija, kas izmanto divus argumentus - sarakstu, kas jāsakārto, un numuru, kas jāmeklē.
• Mēs esam deklarējuši divus mainīgos, lai saglabātu zemākās un augstākās vērtības sarakstā. Zemākajai vērtībai tiek piešķirta sākotnējā vērtība 0, augsts uz len(saraksts1) - 1 un vidus kā 0.
• Tālāk mēs esam paziņojuši kamēr cilpa ar nosacījumu, ka zemākais ir vienāds un mazāks par augstākais Cilpa while atkārtosies, ja numurs vēl nav atrasts.
• Ciklā while mēs atrodam vidējo vērtību un salīdzinām indeksa vērtību ar meklēto skaitli.
• Ja vidējā indeksa vērtība ir mazāka par n , mēs palielinām vidējo vērtību par 1 un piešķiram to Meklēšana pārvietojas uz kreiso pusi.
• Pretējā gadījumā samaziniet vidējo vērtību un piešķiriet to augsts . Meklēšana virzās uz labo pusi.
• Ja n ir vienāds ar vidējo vērtību, atgriezieties vidus .
• Tas notiks līdz plkst zems ir vienāds un mazāks par augsts .
• Ja sasniedzam funkcijas beigās, tad elements sarakstā nav. Mēs atgriežam -1 izsaucējai funkcijai.

Izpratīsim binārās meklēšanas rekursīvo metodi.

Rekursīvā binārā meklēšana

Binārajā meklēšanā var izmantot rekursijas metodi. Šeit mēs definēsim rekursīvu funkciju, kas turpina sevi izsaukt, līdz tā atbilst nosacījumam.

lapsa vai vilks

Sapratīsim iepriekš minēto programmu, izmantojot rekursīvo funkciju.

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

Izvade:

 Element is present at index 2 

Paskaidrojums

Iepriekš minētā programma ir līdzīga iepriekšējai programmai. Mēs deklarējām rekursīvu funkciju un tās pamatnosacījumu. Nosacījums: zemākā vērtība ir mazāka vai vienāda ar augstāko vērtību.

• Mēs aprēķinām vidējo skaitli tāpat kā pēdējā programmā.
• Mēs esam izmantojuši ja paziņojumu, lai turpinātu bināro meklēšanu.
• Ja vidējā vērtība ir vienāda ar meklēto skaitli, tiek atgriezta vidējā vērtība.
• Ja vidējā vērtība ir mazāka par vērtību, mēs meklējam mūsu rekursīvo funkciju binary_search() vēlreiz un palieliniet vidējo vērtību par vienu un piešķiriet zemajai vērtībai.
• Ja vidējā vērtība ir lielāka par vērtību, kuru mēs meklējam, tad mūsu rekursīvā funkcija binary_search() vēlreiz un samaziniet vidējo vērtību par vienu un piešķiriet tai zemai.

Pēdējā daļā mēs esam uzrakstījuši savu galveno programmu. Tā ir tāda pati kā iepriekšējā programmā, taču vienīgā atšķirība ir tā, ka programmā esam nodevuši divus parametrus binary_search() funkciju.

Tas ir tāpēc, ka mēs nevaram piešķirt sākotnējās vērtības rekursīvās funkcijas zemajai, augstajai un vidējai vērtībai. Katru reizi, kad tiek izsaukts rekursīvs, šo mainīgo vērtība tiks atiestatīta. Tas dos nepareizu rezultātu.

Sarežģītība

Binārās meklēšanas algoritma sarežģītība ir O(1) labākajā gadījumā. Tas notiek, ja mūsu meklētais elements atrodams pirmajā salīdzinājumā. The O(pieteikties) ir binārās meklēšanas sliktākā un vidējā sarežģītība. Tas ir atkarīgs no meklējumu skaita, kas tiek veikti, lai atrastu meklēto elementu.

Secinājums

Binārais meklēšanas algoritms ir visefektīvākais un ātrākais veids, kā meklēt elementu sarakstā. Tas izlaiž nevajadzīgu salīdzināšanu. Kā norāda nosaukums, meklēšana ir sadalīta divās daļās. Tas koncentrējas uz saraksta pusi, kas ir tuvu mūsu meklētajam numuram.

Mēs esam apsprieduši abas metodes, lai atrastu dotā skaitļa indeksa pozīciju.