Este tutorial aprenderá como podemos aplicar um algoritmo de pesquisa binária usando Python para encontrar a posição do índice de um elemento na lista fornecida.

Introdução

Uma pesquisa binária é um algoritmo para encontrar um elemento específico na lista. Suponha que temos uma lista de milhares de elementos e precisamos obter uma posição de índice de um elemento específico. Podemos encontrar a posição do índice do elemento muito rapidamente usando o algoritmo de busca binária.

Existem muitos algoritmos de busca, mas a busca binária é o mais popular entre eles.

Os elementos da lista devem ser classificados para aplicar o algoritmo de busca binária. Se os elementos não estiverem classificados, classifique-os primeiro.

Vamos entender o conceito de pesquisa binária.

Conceito de pesquisa binária

No algoritmo de pesquisa binária, podemos encontrar a posição do elemento usando os seguintes métodos.

• Método Recursivo
• Método Iterativo

A técnica de abordagem dividir para conquistar é seguida pelo método recursivo. Neste método, uma função é chamada a si mesma repetidamente até encontrar um elemento na lista.

Um conjunto de instruções é repetido várias vezes para encontrar a posição do índice de um elemento no método iterativo. O enquanto loop é usado para realizar esta tarefa.

A pesquisa binária é mais eficaz que a pesquisa linear porque não precisamos pesquisar cada índice da lista. A lista deve ser classificada para alcançar o algoritmo de pesquisa binária.

Vamos fazer uma implementação passo a passo da pesquisa binária.

Temos uma lista ordenada de elementos e estamos procurando a posição do índice 45.

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

Portanto, estamos definindo duas dicas em nossa lista. Um ponteiro é usado para denotar o valor menor chamado baixo e o segundo ponteiro é usado para denotar o valor mais alto chamado alto .

A seguir, calculamos o valor do meio elemento na matriz.

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

Agora, compararemos o elemento pesquisado com o valor médio do índice. Nesse caso, 32 não é igual a Quatro cinco. Portanto, precisamos fazer mais comparações para encontrar o elemento.

Se o número que estamos pesquisando for igual ao meio. Então volte meio caso contrário, passe para a comparação adicional.

O número a ser pesquisado é maior que o meio número, comparamos o n com o elemento do meio dos elementos do lado direito de meio e ajuste baixo para baixo = médio + 1.

conceitos java oops

Caso contrário, compare o n com o elemento do meio dos elementos do lado esquerdo meio E definir alto para alto = médio - 1.

Repita até que o número que procuramos seja encontrado.

Implementar uma pesquisa binária em Python

Primeiro, implementamos uma pesquisa binária com o método iterativo. Repetiremos um conjunto de instruções e iteraremos cada item da lista. Encontraremos o valor médio até que a pesquisa seja concluída.

Vamos entender o seguinte programa do método iterativo.

Implementação 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ção:

No programa acima -

• Criamos uma função chamada pesquisa_binária() função que leva dois argumentos - uma lista para classificar e um número para pesquisar.
• Declaramos duas variáveis ​​para armazenar os valores mais baixos e mais altos da lista. O valor baixo recebe o valor inicial de 0, alto para len(lista1) - 1 e meio como 0.
• A seguir, declaramos o enquanto loop com a condição de que o mais baixo é igual e menor que o Altíssima O loop while irá iterar se o número ainda não tiver sido encontrado.
• No loop while, encontramos o valor médio e comparamos o valor do índice com o número que estamos procurando.
• Se o valor do índice médio for menor que n , aumentamos o valor médio em 1 e o atribuímos a A pesquisa se move para o lado esquerdo.
• Caso contrário, diminua o valor médio e atribua-o ao alto . A pesquisa se move para o lado direito.
• Se n for igual ao valor médio, retorne meio .
• Isso acontecerá até o baixo é igual e menor que o alto .
• Se chegarmos ao final da função, o elemento não estará presente na lista. Retornamos -1 para a função de chamada.

Vamos entender o método recursivo de pesquisa binária.

Pesquisa binária recursiva

O método de recursão pode ser usado na pesquisa binária. Nisto, definiremos uma função recursiva que continua chamando a si mesma até atender à condição.

árvore binária vs bst

Vamos entender o programa acima usando a função 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') 

Saída:

 Element is present at index 2 

Explicação

O programa acima é semelhante ao programa anterior. Declaramos uma função recursiva e sua condição base. A condição é que o valor mais baixo seja menor ou igual ao valor mais alto.

• Calculamos o número do meio como no último programa.
• Nós usamos o se instrução para prosseguir com a pesquisa binária.
• Se o valor do meio for igual ao número que procuramos, o valor do meio será retornado.
• Se o valor do meio for menor que o valor, estamos procurando nossa função recursiva pesquisa_binária() novamente e aumente o valor médio em um e atribua a baixo.
• Se o valor do meio for maior que o valor que estamos procurando, então nossa função recursiva pesquisa_binária() novamente e diminua o valor médio em um e atribua-o a baixo.

Na última parte, escrevemos nosso programa principal. É igual ao programa anterior, mas a única diferença é que passamos dois parâmetros no pesquisa_binária() função.

Isso ocorre porque não podemos atribuir os valores iniciais para baixo, alto e médio na função recursiva. Cada vez que a recursiva for chamada o valor será zerado para essas variáveis. Isso dará o resultado errado.

Complexidade

A complexidade do algoritmo de pesquisa binária é O(1) para o melhor caso. Isso acontece se o elemento que procuramos for encontrado na primeira comparação. O O(logn) é o pior e a complexidade média do caso da pesquisa binária. Isso depende do número de pesquisas realizadas para encontrar o elemento que procuramos.

Conclusão

Um algoritmo de pesquisa binária é a maneira mais eficiente e rápida de pesquisar um elemento na lista. Isso ignora a comparação desnecessária. Como o nome sugere, a pesquisa é dividida em duas partes. Ele se concentra na lateral da lista, que fica próximo ao número que procuramos.

Discutimos os dois métodos para encontrar a posição do índice de um determinado número.