O que é pesquisa binária?

Uma pesquisa binária é um algoritmo de pesquisa usado para pesquisar elementos de destino em um contêiner onde os elementos devem ser organizados em ordem crescente. Geralmente, a pesquisa binária é usada para pesquisar o número de índice do elemento de destino em uma matriz classificada.

A pesquisa binária usa a abordagem de dividir e conquistas, na qual divide a matriz em partes iguais até encontrar o elemento de destino.

Um algoritmo de pesquisa binário é implementado iterativo e uma declaração recursiva. A pesquisa binária é mais eficiente e mais rápida em comparação com a pesquisa linear.

Algoritmo de pesquisa binária

1. Classifique e organize os elementos da matriz arr em ordem ascendente.
2. Os algoritmos comparam o elemento do meio n com o elemento alvo alvo.
3. O algoritmo retorna o índice de posição do elemento intermediário se o elemento de destino for considerado igual ao elemento do meio,
4. O algoritmo procura a metade inferior da matriz se o elemento alvo for menor que o elemento do meio.
5. O algoritmo procura a metade superior da matriz se o elemento alvo for maior que o elemento do meio.
6. O algoritmo continua repetindo os 4º e 5º passos até que o comprimento da matriz se torne um ou menos de 1.

No final, o valor do índice do elemento é retornado ou o elemento não existe na matriz.

Pseudocódigo de pesquisa binária

Iterativo

function binary_search (arr, n, alvo) é
Esquerda: = 0
Direita: = n - 1
Enquanto esquerda ≤ direita, faça
meio: = piso ((esquerda + direita) / 2)
Se Arr [meio] alvo então
Direita: = Médio - 1
outro:
retornar meio
retornar malsucedido

Recursivo

função binary_search (arr, esquerda, direita, alvo) é
Se direita> = esquerda
meio = (esquerda+direita) // 2
Se arr [meio] == Target
retornar meio
caso contrário, se arr [Middle]> Tarrget
Retornar binário_search (arr, baixo, meados de 1, alvo)
outro
Retornar Binary_search (arr, Mid+1, direita, alvo)
outro
retornar malsucedido

Implementar pesquisa binária no Python

Iterativo
Na abordagem iterativa, usamos os loops para implementar a pesquisa binária.

def binary_search (arr, n, alvo):
Esquerda = 0
direita = n-1
meio = 0
enquanto saiu<=right:
meio = (direita+esquerda) // 2
#Se o elemento do meio é igual ao elemento de destino
Se arr [meio] == Target:
retornar meio
# Se o elemento alvo for maior que o elemento do meio
Elif arr [meio]< target:
Esquerda = Médio+1
# Se o elemento alvo for menor que o elemento do meio
outro:
DIREITO = Médio 1
# Se o elemento de destino não estiver presente na matriz
retornar -1
se __name__ == '__main__':
# Array classificado
STORD_ARR = [0,4,7,10,14,23,45,47,53]
# comprimento da matriz
n = len (classificado_arr)
#Element para pesquisar
Target = 47
Position = binário_search (STORNED_ARR, N, Target)
Se posição != -1:
print (f "elemento Target presente no índice position")
outro:
print (f "Element Target não apresenta na matriz")

Saída

Elemento 47 presente no índice 7

Recursivo
Em recursivo em vez de usar loop, continuamos chamando a função repetidamente até que a condição base seja satisfeita

def binary_search (arr, esquerda, direita, alvo):
#base condição
Se RightTarget:
Retornar binário_search (arr, esquerda, 1, alvo)
#se elemento de destino é menor que o elemento do meio
outro:
Retornar binário_search (arr, médio+1, direita, alvo)
se __name__ == '__main__':
# Array classificado
STORD_ARR = [0,4,7,10,14,23,45,47,53]
Esquerda = 0
direita = len (classificada_arr) -1
#Element para pesquisar
Target = 47
posição = binary_search (classificado_arr, esquerda, direita, alvo)
Se posição != -1:
print (f "elemento Target presente no índice position")
outro:
print (f "Element Target não apresenta na matriz")

Saída

O elemento 90 não está presente na matriz

Complexidade

A pesquisa binária tem uma complexidade de tempo de O (log n), onde n é o número de elementos presentes na matriz.

A pesquisa binária tem uma complexidade espacial de O (1) porque, no algoritmo, estamos realizando a pesquisa no local.

Conclusão

A pesquisa binária é um dos melhores e eficientes algoritmos de pesquisa. A complexidade do tempo e do espaço da pesquisa binária também é muito baixa; O único pré -requisito da pesquisa binária é que a matriz de entrada deve ser classificada em ordem crescente.