TechCodeview

Aquest tutorial aprendrà com podem aplicar un algorisme de cerca binari amb Python per trobar la posició d'índex d'un element a la llista donada.

Introducció

Una cerca binària és un algorisme per trobar un element determinat a la llista. Suposem que tenim una llista de mil elements i hem d'obtenir una posició d'índex d'un element concret. Podem trobar la posició de l'índex de l'element molt ràpidament mitjançant l'algorisme de cerca binària.

Hi ha molts algorismes de cerca, però la cerca binària és la més popular entre ells.

Els elements de la llista s'han d'ordenar per aplicar l'algorisme de cerca binària. Si els elements no estan ordenats, primer ordeneu-los.

Entenem el concepte de cerca binària.

Concepte de cerca binària

En l'algorisme de cerca binària, podem trobar la posició de l'element mitjançant els mètodes següents.

• Mètode recursiu
• Mètode iteratiu

El mètode recursiu segueix la tècnica de l'enfocament de dividir i vencer. En aquest mètode, una funció s'anomena una i altra vegada fins que troba un element a la llista.

Un conjunt d'instruccions es repeteix diverses vegades per trobar la posició d'índex d'un element en el mètode iteratiu. El mentre s'utilitza el bucle per dur a terme aquesta tasca.

La cerca binària és més efectiva que la cerca lineal perquè no necessitem cercar cada índex de llista. La llista s'ha d'ordenar per aconseguir l'algorisme de cerca binària.

Anem a fer una implementació pas a pas de la cerca binària.

Tenim una llista ordenada d'elements i estem buscant la posició d'índex de 45.

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

Sèrie de Fibonacci a Java

Per tant, estem establint dos punters a la nostra llista. S'utilitza un punter per indicar el valor més petit anomenat baix i el segon punter s'utilitza per indicar el valor més alt anomenat alt .

A continuació, calculem el valor de la mig element de la matriu.

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

Ara, compararem l'element cercat amb el valor de l'índex mitjà. En aquest cas, 32 no és igual a 45. Per tant, hem de fer més comparacions per trobar l'element.

Si el nombre que estem cercant és igual al mig. Després torna mig en cas contrari, passeu a la comparació posterior.

El nombre a cercar és més gran que el mig nombre, comparem el n amb l'element central dels elements al costat dret de mig i posa baix a baix = mitjà + 1.

En cas contrari, compareu el n amb el element mitjà dels elements del costat esquerre de mig i posat alt a alt = mitjà - 1.

Repetiu fins que es trobi el número que estem cercant.

Implementar una cerca binària a Python

Primer, implementem una cerca binària amb el mètode iteratiu. Repetirem un conjunt d'afirmacions i repetirem tots els elements de la llista. Trobarem el valor mitjà fins que s'hagi completat la cerca.

Entendrem el següent programa del mètode iteratiu.

Implementació de 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></=>

Explicació:

En el programa anterior -

• Hem creat una funció anomenada cerca_binaria() funció que pren dos arguments: una llista per ordenar i un número per cercar.
• Hem declarat dues variables per emmagatzemar els valors més baix i més alt de la llista. El valor baix s'assigna a 0, alt a len(llista1) - 1 i mitjà com 0.
• A continuació, hem declarat el mentre bucle amb la condició que el més baix és igual i més petit que el més alt El bucle while repetirà si encara no s'ha trobat el número.
• En el bucle while, trobem el valor mitjà i comparem el valor de l'índex amb el nombre que estem cercant.
• Si el valor de l'índex mitjà és menor que n , augmentem el valor mitjà en 1 i l'assignem a La cerca es mou al costat esquerre.
• En cas contrari, reduïu el valor mitjà i assigneu-lo a alt . La cerca es mou cap a la dreta.
• Si n és igual al valor mitjà, retorneu mig .
• Això passarà fins al baix és igual i més petit que el alt .
• Si arribem al final de la funció, llavors l'element no està present a la llista. Tornem -1 a la funció de crida.

Entenem el mètode recursiu de la cerca binària.

Cerca binària recursiva

El mètode de recursivitat es pot utilitzar en la cerca binària. En això, definirem una funció recursiva que segueix cridant-se fins que compleix la condició.

cadena i subcadena

Entenem el programa anterior utilitzant la funció recursiva.

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

Sortida:

 Element is present at index 2 

Explicació

El programa anterior és similar al programa anterior. Hem declarat una funció recursiva i la seva condició base. La condició és que el valor més baix sigui menor o igual al valor més alt.

• Calculem el nombre mitjà com en l'últim programa.
• Hem utilitzat el si declaració per continuar amb la cerca binària.
• Si el valor mitjà és igual al nombre que estem buscant, es retorna el valor mitjà.
• Si el valor mitjà és menor que el valor, estem buscant la nostra funció recursiva cerca_binària() de nou i augmentar el valor mitjà en un i assignar-lo a baix.
• Si el valor mitjà és més gran que el valor que estem buscant, la nostra funció recursiva cerca_binaria() de nou i reduïu el valor mitjà en un i assigneu-lo a baix.

A l'última part, hem escrit el nostre programa principal. És el mateix que el programa anterior, però l'única diferència és que hem passat dos paràmetres al cerca_binària() funció.

Això es deu al fet que no podem assignar els valors inicials als baixos, alts i mitjans de la funció recursiva. Cada vegada que es crida el recursiu, el valor es restablirà per a aquestes variables. Això donarà un resultat equivocat.

Complexitat

La complexitat de l'algorisme de cerca binària és O(1) pel millor dels casos. Això passa si l'element que estem buscant es troba a la primera comparació. El O (inici de sessió) és el pitjor i la complexitat mitjana dels casos de la cerca binària. Això depèn del nombre de cerques que es realitzin per trobar l'element que busquem.

Conclusió

Un algorisme de cerca binari és la forma més eficient i ràpida de cercar un element de la llista. Es salta la comparació innecessària. Com el seu nom indica, la recerca es divideix en dues parts. Se centra en el costat de la llista, que s'aproxima al nombre que estem cercant.

Hem discutit ambdós mètodes per trobar la posició de l'índex del nombre donat.