Pesquisa Binária e sua importância
O que é Pesquisa binária?
A pesquisa binária é um método eficiente para encontrar um elemento em uma lista ordenada de elementos. Ela se baseia no princípio de divisão e conquista, que consiste em reduzir o problema em subproblemas menores e mais fáceis de resolver. Neste artigo, vamos explicar como funciona a pesquisa binária e como ela pode ser implementada em um código de programação.
A ideia da pesquisa binária é comparar o elemento buscado com o elemento do meio da lista. Se eles forem iguais, a busca termina com sucesso. Se o elemento buscado for menor que o elemento do meio, a busca continua na metade esquerda da lista. Se o elemento buscado for maior que o elemento do meio, a busca continua na metade direita da lista. Esse processo se repete até que o elemento seja encontrado ou que a lista esteja vazia.
Para ilustrar esse algoritmo, vamos usar um exemplo simples. Suponha que temos uma lista de números ordenados de 1 a 10 e queremos encontrar o número 7. A lista é a seguinte:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
O primeiro passo é comparar o número 7 com o elemento do meio da lista, que é o número 5. Como 7 é maior que 5, descartamos a metade esquerda da lista e continuamos a busca na metade direita:
[6, 7, 8, 9, 10]
O segundo passo é comparar o número 7 com o elemento do meio da nova lista, que é o número 8. Como 7 é menor que 8, descartamos a metade direita da lista e continuamos a busca na metade esquerda:
[6, 7]
O terceiro passo é comparar o número 7 com o elemento do meio da nova lista, que é o próprio número 7. Como eles são iguais, a busca termina com sucesso e retornamos o índice do elemento encontrado, que é 6.
A pesquisa binária pode ser implementada em diferentes linguagens de programação, mas a lógica é basicamente a mesma. Vamos mostrar um exemplo de código em Python, que é uma linguagem simples e popular:
Definindo uma função que recebe uma lista ordenada e um elemento a ser buscado
def pesquisa_binaria(lista, elemento): # Definindo os limites inferior e superior da busca inicio = 0 fim = len(lista) - 1 # Enquanto os limites não se cruzarem while inicio <= fim: # Calculando o índice do meio da lista meio = (inicio + fim) // 2 # Comparando o elemento do meio com o elemento buscado if lista[meio] == elemento: # Se forem iguais, retorna o índice do meio return meio elif lista[meio] < elemento: # Se o elemento do meio for menor que o elemento buscado, # move o limite inferior para uma posição depois do meio inicio = meio + 1 else: # Se o elemento do meio for maior que o elemento buscado, # move o limite superior para uma posição antes do meio fim = meio - 1 # Se os limites se cruzarem e não encontrar o elemento, # retorna -1 para indicar que não foi encontrado return -1
Testando a função com uma lista de números ordenados de 1 a 10
lista = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] elemento = 7
Chamando a função e imprimindo o resultado
resultado = pesquisa_binaria(lista, elemento) print(resultado)
