Implementar um mecanismo de busca pode ser um desafio, mas certamente não é uma tarefa impossível.
No dia a dia, não seguimos um padrão específico ao procurar algo. Geralmente, exploramos lugares onde acreditamos que o que buscamos pode estar. Ou seja, não nos guiamos por um método estruturado na maioria das situações.
Mas essa mesma abordagem funciona no contexto da programação?
A resposta é não! Na programação, precisamos de um padrão para localizar dados. Neste artigo, vamos explorar alguns algoritmos que seguem diferentes padrões de busca.
Existem diversos algoritmos disponíveis no mundo da programação. Neste texto, abordaremos os mais importantes e frequentemente usados. Compreender esses algoritmos básicos tornará o aprendizado dos demais muito mais fácil.
Neste artigo, o foco da busca será a localização de um elemento específico dentro de um array.
Vamos analisar cada um deles detalhadamente.
Busca Linear
Como o nome sugere, a busca linear utiliza uma abordagem sequencial para encontrar elementos em um array. O algoritmo começa a procura pelo elemento desejado a partir do início do array e segue até o final, até que o encontre. A execução é interrompida no momento em que o elemento é localizado.
Para facilitar a compreensão, vamos ilustrar o funcionamento da busca linear com exemplos visuais.
Observando o padrão de busca, podemos notar que o tempo de execução, no pior cenário, será O(n). Ao analisar algoritmos, é crucial considerar sua complexidade de tempo no pior caso. Portanto, a complexidade de tempo da busca linear é O(n).
Agora, vamos à implementação da busca linear.
Implementação da Busca Linear
Após essa explicação, você já deve ter uma boa compreensão da busca linear. É hora de colocar a mão na massa com um pouco de código. Vamos começar com os passos para implementar a busca linear. Depois, você pode tentar codificá-lo. E não se preocupe se não conseguir de primeira; vou fornecer o código logo em seguida.
Aqui estão os passos para implementar o algoritmo de busca linear:
- Crie um array com elementos (seus números da sorte, por exemplo).
- Defina uma função chamada `search_element` que receba três parâmetros: o array, o tamanho do array e o elemento que se deseja encontrar.
- Na função `search_element(arr, n, elemento)`:
- Itere sobre o array.
- Verifique se o elemento atual é igual ao elemento procurado.
- Se forem iguais, retorne `True`.
- Se o loop for concluído sem encontrar o elemento, significa que ele não está presente no array. Portanto, retorne `False`.
- Itere sobre o array.
- Exiba uma mensagem com base no valor retornado pela função `search_element`.
Agora, com base nos passos acima, escreva o código para implementar a busca linear.
Conseguiu implementar o algoritmo de busca linear? Espero que sim! Se conseguiu, compare seu código com o que será apresentado abaixo.
Se ainda não concluiu, não se preocupe; veja o código abaixo e entenda como implementá-lo. Você conseguirá sem muito esforço.
## Função de busca
def search_element(arr, n, element):
## Iterando pelo array
for i in range(n):
## Verificando se o elemento atual é o desejado
if arr[i] == element:
## Retornando True se houver correspondência
return True
## Se o elemento não for encontrado, a execução chega aqui
return False
if __name__ == '__main__':
## Inicializando o array, o tamanho e o elemento a ser buscado
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 10
element_to_be_searched = 6
# element_to_be_searched = 11
if search_element(arr, n, element_to_be_searched):
print(element_to_be_searched, "foi encontrado")
else:
print(element_to_be_searched, "não foi encontrado")
Primeiro, execute o programa com um elemento que está no array. Depois, execute-o com um elemento que não está.
A complexidade de tempo do algoritmo de busca linear é O(n).
Podemos melhorar um pouco essa eficiência usando padrões diferentes?
Sim, podemos. Vamos ver como.
Busca Binária
O algoritmo de busca binária sempre verifica o elemento do meio do array. Esse algoritmo é utilizado em arrays que já estão ordenados.
A busca binária itera sobre o array e verifica o elemento central. Se o elemento for encontrado, o programa é finalizado. Caso contrário, se o elemento do meio for menor do que o elemento procurado, a busca é feita na parte direita do array. Se o elemento do meio for maior, a busca continua na parte esquerda do array.
A cada iteração, o algoritmo de busca binária reduz a área onde o elemento pode estar. Isso faz com que o número de verificações seja menor do que na busca linear.
Ilustrações podem nos ajudar a compreender melhor esse algoritmo. Vamos a elas.
A complexidade de tempo da busca binária é O(log n). A cada iteração, a área de busca é reduzida pela metade. Essa redução é exponencial.
Implementação da Busca Binária
Primeiro, veremos os passos para implementar a busca binária e depois o código. Vamos aos passos para implementar o algoritmo de busca binária:
- Crie um array com elementos já ordenados (seus números da sorte, por exemplo).
- Defina uma função chamada `search_element`, que recebe três argumentos: o array ordenado, o tamanho do array e o elemento a ser procurado.
- Na função `search_element(sorted_arr, n, element)`:
- Inicialize uma variável de índice `i` para iterar sobre o array.
- Inicialize duas variáveis para controlar a área de busca do array. Chamaremos essas variáveis de `inicio` e `fim`, pois elas indicam os índices.
- Itere enquanto `i` for menor que o tamanho do array.
- Calcule o índice do meio da área de busca utilizando os valores de `inicio` e `fim`. Isso será `(inicio + fim) // 2`.
- Verifique se o elemento indexado do meio da área de busca é igual ao elemento desejado.
- Se forem iguais, retorne `True`.
- Caso contrário, se o elemento do meio for menor que o elemento procurado, mova o índice `inicio` da área de busca para `meio + 1`.
- Caso contrário, se o elemento do meio for maior que o elemento procurado, mova o índice `fim` da área de busca para `meio – 1`.
- Incremente o índice `i` do array.
- Se o loop for concluído sem encontrar o elemento, significa que ele não está presente no array. Portanto, retorne `False`.
- Exiba uma mensagem com base no valor retornado pela função `search_element`.
Tente escrever o código seguindo a implementação da busca linear.
…
Conseguiu escrever o código?
Se sim, compare com o código abaixo. Se não, não se preocupe; entenda a implementação com o código abaixo:
## Função de busca
def search_element(sorted_arr, n, element):
## Índice do array para iteração
i = 0
## Variáveis para controlar a área de busca
## Inicializando com os índices de início e fim
start = 0
end = n - 1
## Iterando sobre o array
while i < n:
## Obtendo o índice do elemento do meio
middle = (start + end) // 2
## Verificando se o elemento do meio é o desejado
if sorted_arr[middle] == element:
## Retornando True, pois o elemento está no array
return True
elif sorted_arr[middle] < element:
## Movendo o índice de início da área de busca para a direita
start = middle + 1
else:
## Movendo o índice de fim da área de busca para a esquerda
end = middle - 1
i += 1
return False
if __name__ == '__main__':
## Inicializando o array, o tamanho e o elemento a ser buscado
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 10
element_to_be_searched = 9
# element_to_be_searched = 11
if search_element(arr, n, element_to_be_searched):
print(element_to_be_searched, "foi encontrado")
else:
print(element_to_be_searched, "não foi encontrado")
Teste o código com casos em que o elemento está presente e em outros em que está ausente.
Conclusão
O algoritmo de busca binária é muito mais eficiente que o algoritmo de busca linear. Para utilizá-lo, é necessário que o array esteja ordenado, o que não é um requisito da busca linear. A ordenação demanda tempo, mas o uso de algoritmos eficientes de ordenação, em conjunto com a busca binária, resulta em uma ótima combinação.
Agora você tem um bom conhecimento dos algoritmos de busca mais utilizados em Python.
Em seguida, explore alguns softwares de busca auto-hospedados populares.
Boa codificação 🙂 🧑💻