Implementações de algoritmos de pesquisa em Python

Implementar a pesquisa é sempre desafiador, mas não impossível.

Na vida real, não buscaremos em nenhum padrão. Nós apenas vamos para os lugares onde achamos 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 algum padrão para pesquisar coisas em programas. Veremos alguns algoritmos que seguem padrões diferentes de pesquisa 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á muito fácil para você aprender.

A pesquisa refere-se a procurando um elemento no array neste artigo.

Vamos vê-los um por um.

Pesquisa linear

O nome sugere que o algoritmo de busca linear segue o linear padronizar para pesquisar os elementos em uma matriz. O algoritmo começa a procurar o 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 o algoritmos de busca linear com algumas ilustrações legais para uma melhor compreensão do algoritmo.

Se você observar cuidadosamente o padrão de pesquisa, verá que o tempo que leva para a execução do programa levará Sobre) no pior caso. Temos que considerar a complexidade de tempo do pior caso dos algoritmos a serem analisados. Portanto, a complexidade de tempo do algoritmo é Sobre).

Vamos ver a implementação do algoritmo de busca linear.

Implementação de pesquisa linear

Agora, você tem uma boa compreensão 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 possa; Eu te passo o código depois.

Vamos ver 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, então retorne Verdadeiro.
  • Após completar o loop, se a execução ainda estiver na função, então o elemento não está presente no array. Daí retornar Falso.
• Imprima a mensagem com base no valor de retorno da função search_element.

Finalmente, escreva o código com a ajuda dos passos acima para implementar o algoritmo de busca linear.

Você concluiu a implementação do algoritmo de busca linear? Espero que sim. Se você tiver concluído, verifique com o código a seguir.

Se você não completou, 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 que está presente no array. E em seguida, execute-o com um elemento que não está presente no array.

A complexidade de tempo do algoritmo de busca linear é Sobre).

Podemos reduzi-lo um pouco mais com padrões diferentes?

Sim, podemos. Vamos ver isso.

Pesquisa binária

o algoritmo de busca binária sempre verifica o elemento do meio do array. Este algoritmo procura o elemento em um matriz ordenada.

o algoritmo de busca binária itera sobre a matriz e verifica o elemento do meio, se encontrado, e 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 buscar o elemento. Assim, o número de verificações é menor que o número de verificações feitas no algoritmo de busca linear.

As 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 os passos para completar a implementação do algoritmo de busca binária.

• Inicialize o array com elementos (seus números da sorte)
• Escreva uma função chamada search_element, que aceita três argumentos, array ordenado, comprimento do array e elemento a ser pesquisado.
• search_element(sorted_arr, n, elemento):
  • Inicialize a variável de índice eu para iteração de matriz.
  • Em seguida, inicialize duas variáveis ​​para manter a área de pesquisa do array. Aqui, nós os chamamos de começar e fim pois indicam índices.
  • Iterar até o eu é menor que o comprimento da matriz.
    • Calcule o índice do meio da área de pesquisa usando o começar e fim valores. 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, então retorne Verdadeiro.
    • Caso contrário, se o elemento indexado do meio for menor que o elemento necessário, mova o começar índice da área de pesquisa para meio + 1.
    • Caso contrário, se o elemento indexado do meio for maior que o elemento necessário, mova o fim índice da área de pesquisa para meio – 1.
    • Incrementar o índice do array eu.
  • Após completar o loop, se a execução ainda estiver na função, então o elemento não está presente no array. Daí retornar 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 busca 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 não está presente em alguns casos.

Conclusão

o algoritmo de busca binária é muito mais eficiente do que o algoritmo de busca linear. Precisamos ordenar o array para o algoritmo de busca binária não é o caso do algoritmo de busca linear. A classificação leva algum tempo. Mas, o uso de algoritmos eficientes para ordenaçã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 🙂 🧑‍💻