A implementação da pesquisa é sempre desafiadora, mas não impossível.
Na vida real, não buscaremos nenhum padrão. Nós apenas vamos para os lugares onde pensamos que pode ser colocado. Não seguimos nenhum padrão na maioria dos casos.
A mesma coisa funciona no mundo da programação?
Não! tem que ter algum padrão para procurar coisas nos programas. Veremos alguns algoritmos que seguem diferentes padrões de busca neste artigo.
Existem vários algoritmos que podemos encontrar no mundo da programação. Vamos discutir os algoritmos mais importantes e mais usados neste artigo. E o resto dos algoritmos será moleza para você aprender.
Pesquisar refere-se à pesquisa de um elemento na matriz neste artigo.
Vamos vê-los um por um.
últimas postagens
Pesquisa Linear
O nome sugere que o algoritmo de busca linear segue o padrão linear para pesquisar os elementos em uma matriz. O algoritmo inicia a busca do elemento desde o início do array e vai até o final até encontrar o elemento. Ele interrompe a execução do programa quando encontra o elemento necessário.
Vamos ilustrar os algoritmos de busca linear com algumas ilustrações interessantes para uma melhor compreensão do algoritmo.
Se você observar cuidadosamente o padrão de busca, descobrirá que o tempo necessário para a execução do programa será O(n) no pior caso. Temos que considerar a complexidade de tempo de pior caso dos algoritmos para analisar. Portanto, a complexidade de tempo do algoritmo é O(n).
Vamos ver a implementação do algoritmo de busca linear.
Implementação de Pesquisa Linear
Agora, você tem um bom entendimento do algoritmo de busca linear. É hora de sujar as mãos com algum código. Vamos ver as etapas para implementar a pesquisa linear primeiro. Então você tenta codificá-lo. Não se preocupe mesmo que não consiga; Vou te passar o código depois.
Vejamos os passos para implementar o algoritmo de busca linear.
- Inicialize uma matriz de elementos (seus números da sorte).
- Escreva uma função chamada search_element, que aceita três argumentos, array, comprimento do array e elemento a ser pesquisado.
- search_element(arr, n, elemento):
- Iterar sobre a matriz fornecida.
- Verifique se o elemento atual é igual ao elemento necessário.
- Se sim, retorne True.
- Depois de completar o loop, se a execução ainda estiver na função, o elemento não estará presente na matriz. Portanto, retorne Falso.
- Iterar sobre a matriz fornecida.
- Imprima a mensagem com base no valor de retorno da função search_element.
Finalmente, escreva o código com a ajuda das etapas acima para implementar o algoritmo de busca linear.
Você completou a implementação do algoritmo de busca linear? Espero que sim. Se você completou, verifique com o código a seguir.
Se você não concluiu, não se preocupe; veja o código abaixo e saiba como o implementamos. Você vai conseguir sem muito esforço.
## searching function def search_element(arr, n, element): ## iterating through the array for i in range(n): ## checking the current element with required element if arr[i] == element: ## returning True on match return True ## element is not found hence the execution comes here return False if __name__ == '__main__': ## initializing the array, length, and element to be searched 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, "is found") else: print(element_to_be_searched, "is not found")
Primeiro, execute o programa com um elemento presente na matriz. E a seguir, execute-o com um elemento que não esteja presente no array.
A complexidade de tempo do algoritmo de busca linear é O(n).
Podemos reduzi-lo um pouco mais com padrões diferentes?
Sim, nós podemos. Vamos ver isso.
Pesquisa binária
O algoritmo de busca binária sempre verifica o elemento do meio da matriz. Este algoritmo pesquisa o elemento em uma matriz classificada.
O algoritmo de busca binária itera sobre o array e verifica o elemento do meio, se encontrado, então para o programa. Caso contrário, se o elemento do meio for menor que o elemento necessário, ele omitirá a parte esquerda da matriz do elemento do meio da pesquisa. Caso contrário, se o elemento do meio for maior que o elemento necessário, ele omitirá a parte direita da matriz do elemento do meio da pesquisa.
Em cada iteração, o algoritmo de busca binária reduz a área para pesquisar o elemento. Portanto, o número de verificações é menor que o número de verificações feitas no algoritmo de busca linear.
Ilustrações nos ajudam a entender melhor o algoritmo de busca binária. Vamos verificá-los.
A complexidade de tempo do algoritmo de busca binária é O(log n). Em cada iteração, o comprimento da área de busca é reduzido pela metade. Está diminuindo exponencialmente.
Implementação de pesquisa binária
Primeiro, veremos os passos para implementar o algoritmo de busca binária e depois o código. Vamos ver as etapas para concluir a implementação do algoritmo de pesquisa binária.
- Inicialize a matriz com elementos (seus números da sorte)
- Escreva uma função chamada search_element, que aceita três argumentos, array classificado, comprimento do array e elemento a ser pesquisado.
- search_element(sorted_arr, n, elemento):
- Inicialize a variável de índice i para iteração do array.
- Em seguida, inicialize duas variáveis para manter a área de pesquisa do array. Aqui, nós os chamamos de início e fim, pois indicam índices.
- Iterar até que i seja menor que o comprimento do array.
- Calcule o índice do meio da área de pesquisa usando os valores inicial e final. Isso será (início + fim) // 2.
- Verifique se o elemento indexado do meio da área de pesquisa é igual ao elemento necessário ou não.
- Se sim, retorne True.
- Caso contrário, se o elemento indexado do meio for menor que o elemento necessário, mova o índice inicial da área de pesquisa para o meio + 1.
- Caso contrário, se o elemento indexado do meio for maior que o elemento necessário, mova o índice final da área de pesquisa para o meio – 1.
- Incrementa o índice do array i.
- Depois de completar o loop, se a execução ainda estiver na função, o elemento não estará presente na matriz. Portanto, retorne Falso.
- Imprima a mensagem com base no valor de retorno da função search_element.
Tente escrever o código semelhante à implementação do algoritmo de pesquisa linear.
…
Você conseguiu o código?
Sim, compare com o código abaixo. Não, não se preocupe; entenda a implementação com o código abaixo.
## searching function def search_element(sorted_arr, n, element): ## array index for iteration i = 0 ## variables to track the search area ## initializing them with start and end indexes start = 0 end = n - 1 ## iterating over the array while i < n: ## getting the index of the middle element middle = (start + end) // 2 ## checking the middle element with required element if sorted_arr[middle] == element: ## returning True since the element is in the array return True elif sorted_arr[middle] < element: ## moving the start index of the search area to right start = middle + 1 else: ## moving the end index of the search area to left end = middle - 1 i += 1 return False if __name__ == '__main__': ## initializing the array, length, and element to be searched 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, "is found") else: print(element_to_be_searched, "is not found")
Teste o código com diferentes casos em que o elemento está presente e ausente em alguns casos.
Conclusão
O algoritmo de busca binária é muito mais eficiente do que o algoritmo de busca linear. Precisamos classificar a matriz para o algoritmo de pesquisa binária não é o caso do algoritmo de pesquisa linear. A classificação leva algum tempo. Porém, usar algoritmos eficientes para classificação formará uma boa combinação com o algoritmo de busca binária.
Agora você tem um bom conhecimento dos algoritmos mais usados em Python.
Em seguida, descubra alguns dos populares softwares de pesquisa auto-hospedados.
Boa codificação 🙂 🧑💻