Pesquisa binária em Python

Este artigo mostrará como usar o Python para realizar uma técnica de pesquisa binária para localizar a posição de índice de uma entidade em uma lista.

Uma pesquisa binária é uma maneira de encontrar um certo elemento dentro de uma lista. Vamos imaginar que temos uma lista de dez mil e elementos e precisamos encontrar a posição do índice de uma única entrada. Podemos encontrar rapidamente a localização do índice de um elemento usando a técnica de pesquisa binária. Outros algoritmos de pesquisa existem, mas o mais amplamente empregado é uma pesquisa binária. Classifique os objetos primeiro se eles ainda não foram classificados.

O algoritmo de busca binária abordagens recursivas e iterativas pode ser utilizada para encontrar a posição do elemento. A estratégia recursiva é usada após a abordagem de divisão e conquista. Dessa maneira, uma função é executada até encontrar um elemento na lista. Para descobrir o local do índice de um elemento, a técnica iterativa repete repetidamente um conjunto de palavras. Este processo é realizado usando o loop while. Como não precisamos pesquisar cada índice de lista, a pesquisa binária é mais eficiente do que a pesquisa linear.

Vamos começar com um entendimento básico da pesquisa binária.

Exemplo 1:

Primeiro, usamos a abordagem iterativa para implementar uma pesquisa binária. Vamos percorrer a lista, repetindo uma sequência de declarações. Continuaremos procurando o valor central até encontrá -lo.

Esta é uma implementação Python da abordagem iterativa da função de pesquisa binária. Se 'Search_num' estiver presente na lista especificada, ele retornará um; Caso contrário, dá -1. Construímos a função de pesquisa binária () neste programa, que aceita dois argumentos: uma lista para classificar e um número para pesquisar. Configuramos duas variáveis ​​para acompanhar os valores mais baixos e maiores da lista. O baixo tem um valor inicial de 0, o alto tem um valor de Len (List1) - 1, e o meio tem um valor de 0. O loop while é então escrito com a restrição de que os mais baixos iguais e são menores que o mais alto. O loop do tempo irá iterar se o número ainda não foi encontrado. O ponto médio é encontrado no while loop. Em seguida, correspondemos ao valor do índice com o número que estamos procurando. Se o valor do índice médio for menor que 'pesquisa num', atribuímos e aumentamos o valor do índice médio por um. O foco da pesquisa muda para a esquerda. Defina o valor médio ao máximo se for alto. Retornar meio se o 'Search_num' for igual ao valor médio. Isso continuará até que o baixo e o alto seja igual e o baixo seja menor que o alto. Se chegarmos ao final da função, sabemos que o elemento não está na lista. Para a função de invasão, retornamos -1.

def binary_search (um, search_num):
baixo = 0
alto = len (um) - 1
MID = 0
enquanto baixo <= high:
MID = (alto + baixo) // 2
Se um [mid] search_num:
High = Mid - 1
outro:
retornar meio
retornar -1
um = [19, 23, 43, 56, 65, 71, 80]
Search_num = 43
output = binary_search (um, search_num)
se saída != -1:
print ("elemento está no índice", str (saída))
outro:
print ("Elemento não está disponível na lista")

Aqui você pode ver que o número necessário é encontrado na posição de índice 2.

Exemplo 2:

Vejamos a abordagem de pesquisa binária recursiva. A abordagem de recursão pode ser usada na pesquisa binária. Faremos uma função recursiva que se chama até que a condição seja satisfeita. O programa anterior é semelhante ao antes. Uma função recursiva, bem como sua condição de base, foram declarados. Calculamos o número do meio como fizemos no programa anterior. Para continuar com a pesquisa binária, usamos a instrução IF. Será retornado se o valor médio for equivalente ao número que estamos procurando. Se o valor médio estiver abaixo do valor, aumentamos em um e o atribuímos a baixo usando nossa função recursiva de pesquisa binária (). Escrevemos nosso programa principal na última seção. O procedimento de pesquisa binária () agora requer 2 parâmetros, que é a única modificação do programa anterior. A incapacidade da função recursiva de atribuir valores iniciais ao baixo, alto e médio é a razão por trás disso. O valor para essas variáveis ​​será redefinido toda vez que a recursão é chamada.

def binary_search (um, baixo, alto, search_num):
Se Low Search_num:
Retorne binário_search (um, baixo, meados - 1, search_num)
outro:
Retornar Binário_search (um, Mid + 1, High, Search_num)
outro:
retornar -1
um = [19, 23, 43, 56, 65, 71, 80]
Search_num = 65
output = binary_search (um, 0, len (um) -1, search_num)
Se Search_num != -1:
print ("elemento está no índice", str (saída))
outro:
print ("Elemento não está disponível na lista")

O valor necessário está no índice 4, como você pode ver na imagem a seguir.

Exemplo 3:

Outro exemplo de uma técnica de pesquisa binária, comumente conhecida como algoritmo de pesquisa de meio interval, é usada para localizar um valor alvo em uma matriz classificada. Este programa retorna verdadeiro se o número estiver localizado na lista.

def binary_search (my_list, search_num):
um = 0
final = len (my_list) -1
encontrado = falso
enquanto (um<=final and not found):
MID = (um + final) // 2
se my_list [mid] == Search_num:
encontrado = true
outro:
Se Search_numFinal = Mid - 1
outro:
um = meio + 1
retorno encontrado
Print (binário_search ([1,2,3,4,5], 3)))
Print (binário_search ([11,22,33,44,55], 5)))

Abaixo está a saída.

Conclusão:

A abordagem mais eficaz e rápida para procurar uma entrada em uma lista é usar um algoritmo de pesquisa binária. Ele pula sobre a analogia sem sentido. Como diz o nome, a pesquisa é dividida em duas peças. Ele se concentra no lado da lista mais próximo do número que estamos procurando. Na melhor situação, a complexidade do algoritmo de busca binária é O (1). Isso ocorre quando o elemento que estamos procurando aparece na primeira comparação. A pior e média a complexidade de casos da pesquisa binária é O (logn). O número total de pesquisas necessárias para localizar o item determina isso. Diferentes abordagens para determinar a posição do índice de um determinado número foram discutidas.