TechCodeview

Acest tutorial va învăța cum putem aplica un algoritm de căutare binar folosind Python pentru a găsi poziția indexului unui element în lista dată.

Introducere

O căutare binară este un algoritm pentru a găsi un anumit element din listă. Să presupunem că avem o listă de mii de elemente și trebuie să obținem o poziție index a unui anumit element. Putem găsi poziția indexului elementului foarte rapid folosind algoritmul de căutare binar.

Există mulți algoritmi de căutare, dar căutarea binară este cea mai populară printre aceștia.

python sortând tupluri

Elementele din listă trebuie sortate pentru a aplica algoritmul de căutare binar. Dacă elementele nu sunt sortate, sortați-le mai întâi.

Să înțelegem conceptul de căutare binară.

Conceptul de căutare binară

În algoritmul de căutare binar, putem găsi poziția elementului folosind următoarele metode.

• Metoda recursiva
• Metoda iterativă

Tehnica abordării împărțiți și cuceriți este urmată de metoda recursivă. În această metodă, o funcție este numită ea însăși din nou și din nou până când a găsit un element în listă.

Un set de instrucțiuni este repetat de mai multe ori pentru a găsi poziția indexului unui element în metoda iterativă. The in timp ce bucla este folosită pentru a îndeplini această sarcină.

Căutarea binară este mai eficientă decât căutarea liniară, deoarece nu trebuie să căutăm fiecare index de listă. Lista trebuie sortată pentru a realiza algoritmul de căutare binar.

Să avem o implementare pas cu pas a căutării binare.

Avem o listă sortată de elemente și căutăm poziția de index de 45.

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

Deci, setăm două indicatoare în lista noastră. Un indicator este folosit pentru a indica valoarea mai mică numită scăzut iar al doilea indicator este folosit pentru a indica cea mai mare valoare apelată înalt .

Apoi, calculăm valoarea lui mijloc element din matrice.

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

Acum, vom compara elementul căutat cu valoarea medie a indexului. În acest caz, 32 nu este egal cu Patru cinci. Deci trebuie să facem o comparație suplimentară pentru a găsi elementul.

Dacă numărul pe care îl căutăm este egal cu mijlocul. Apoi întoarce-te mijlocul în caz contrar trece la comparația ulterioară.

Numărul de căutat este mai mare decât mijloc număr, comparăm n cu elementul mijlociu al elementelor pe partea dreaptă a mijlocul și setați jos la scăzut = mijloc + 1.

În caz contrar, comparați n cu element de mijloc a elementelor din partea stângă a mijlocul și setați înalt la ridicat = mijloc - 1.

Repetați până când este găsit numărul pe care îl căutăm.

Implementați o căutare binară în Python

În primul rând, implementăm o căutare binară cu metoda iterativă. Vom repeta un set de afirmații și vom repeta fiecare element din listă. Vom găsi valoarea de mijloc până când căutarea este completă.

Să înțelegem următorul program al metodei iterative.

metoda tostring

Implementarea Python

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

Explicaţie:

În programul de mai sus -

• Am creat o funcție numită binary_search() funcție care ia două argumente - o listă de sortat și un număr de căutat.
• Am declarat două variabile pentru a stoca cele mai mici și cele mai mari valori din listă. Valoarea inițială scăzută este atribuită la 0, înalt la len(lista1) - 1 și mijloc ca 0.
• În continuare, am declarat in timp ce buclă cu condiția ca cel mai jos este egală și mai mică decât cel mai inalt Bucla while se va repeta dacă numărul nu a fost încă găsit.
• În bucla while, găsim valoarea medie și comparăm valoarea indexului cu numărul pe care îl căutăm.
• Dacă valoarea indicelui mijlociu este mai mică decât n , creștem valoarea medie cu 1 și o atribuim Căutarea se deplasează în partea stângă.
• În caz contrar, reduceți valoarea medie și atribuiți-o înalt . Căutarea se deplasează în partea dreaptă.
• Dacă n este egal cu valoarea mijlocie, reveniți mijlocul .
• Acest lucru se va întâmpla până la scăzut este egală și mai mică decât înalt .
• Dacă ajungem la sfârșitul funcției, atunci elementul nu este prezent în listă. Revenim -1 la funcția de apelare.

Să înțelegem metoda recursivă a căutării binare.

Căutare binară recursiv

Metoda recursiunii poate fi folosită în căutarea binară. În aceasta, vom defini o funcție recursivă care continuă să se numească până când îndeplinește condiția.

Să înțelegem programul de mai sus folosind funcția recursivă.

Programul Python

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

Ieșire:

 Element is present at index 2 

Explicaţie

Programul de mai sus este similar cu programul anterior. Am declarat o funcție recursivă și condiția ei de bază. Condiția este valoarea cea mai mică este mai mică sau egală cu valoarea cea mai mare.

• Calculăm numărul din mijloc ca în ultimul program.
• Am folosit dacă instrucțiune pentru a continua căutarea binară.
• Dacă valoarea de mijloc este egală cu numărul pe care îl căutăm, se returnează valoarea de mijloc.
• Dacă valoarea din mijloc este mai mică decât valoarea, atunci căutăm funcția noastră recursivă binary_search() din nou și măriți valoarea medie cu unu și atribuiți-o la low.
• Dacă valoarea din mijloc este mai mare decât valoarea pe care o căutăm, atunci funcția noastră recursivă binary_search() din nou și micșorați valoarea medie cu unu și atribuiți-o la low.

În ultima parte, am scris programul nostru principal. Este același cu programul anterior, dar singura diferență este că am trecut doi parametri în binary_search() funcţie.

Acest lucru se datorează faptului că nu putem aloca valorile inițiale la low, high și mid în funcția recursivă. De fiecare dată când recursiv este apelat valoarea va fi resetat pentru acele variabile. Asta va da un rezultat greșit.

Complexitate

Complexitatea algoritmului de căutare binar este O(1) pentru cel mai bun caz. Acest lucru se întâmplă dacă elementul pe care îl căutăm îl găsește în prima comparație. The O(logn) este cea mai proastă și complexitatea medie de caz a căutării binare. Aceasta depinde de numărul de căutări efectuate pentru a găsi elementul pe care îl căutăm.

Concluzie

Un algoritm de căutare binar este cel mai eficient și rapid mod de a căuta un element din listă. Omite comparația inutilă. După cum sugerează și numele, căutarea este împărțită în două părți. Se concentrează pe partea listei, care este aproape de numărul pe care îl căutăm.

sunny deol age

Am discutat ambele metode pentru a găsi poziția de index a numărului dat.