Um dos algoritmos mais fundamentais na ciência da computação é o algoritmo de busca binária. Você pode implementar a Pesquisa Binária usando dois métodos: o método iterativo e o método recursivo. Embora ambos os métodos tenham a mesma complexidade de tempo, o método iterativo é muito mais eficiente em termos de complexidade de espaço.
O método iterativo tem uma complexidade espacial de O(1) em comparação com O(logn) produzidos pelo método recursivo. Então, como você pode implementar o algoritmo Binary Search usando o método iterativo em C, C++ e Python?
O que é pesquisa binária?
A pesquisa binária, também conhecida como pesquisa de meio intervalo, pesquisa logarítmica ou divisão binária, é um algoritmo que pesquisa e retorna a posição de um elemento em uma matriz classificada. O elemento de pesquisa é comparado ao elemento do meio. Tomando a média dos limites inferior e superior, você pode encontrar os elementos intermediários.
Se o elemento de pesquisa for maior que o elemento do meio, significa que todos os elementos do lado esquerdo são menores que o elemento de pesquisa. Assim, o controle muda para o lado direito do array (se o array estiver em ordem crescente) aumentando o limite inferior para a próxima posição do elemento do meio.
Da mesma forma, se o elemento de pesquisa for menor que o elemento do meio, significa que todos os elementos do lado direito são maiores que o elemento de pesquisa. Assim, o controle se desloca para a parte esquerda da matriz alterando o limite superior para a posição anterior do elemento do meio.
Isso reduz drasticamente o número de comparações em comparação com implementação de pesquisa linear onde o número de comparações é igual ao número de elementos no pior cenário. Este método é muito útil para encontrar números em uma lista telefônica ou palavras em um dicionário.
Aqui está uma representação esquemática do Algoritmo de pesquisa binária:
Pesquisa Binária Usando C
Siga estas etapas para implementar a pesquisa binária usando C:
Todo o código-fonte do programa de pesquisa binária usando C, C++, Java e Python está presente neste Repositório GitHub.
O programa define uma função, binarySearch(), que retorna o índice do valor encontrado ou -1 se não estiver presente:
#incluir <stdio.h>
intbusca binária(int arr[], int arr_size, int pesquisar_número){
/*... */
}
A função funciona estreitando iterativamente o espaço de pesquisa. Como a pesquisa binária funciona em matrizes classificadas, você pode calcular o meio que, de outra forma, não faria sentido. Você pode solicitar ao usuário uma matriz classificada ou usar algoritmos de classificação, como Bubble ou Selection sort.
O baixo e alto as variáveis armazenam os índices que representam os limites do espaço de pesquisa atual. meio armazena o índice no meio:
int baixo = 0, alto = arr_size - 1, meio;O principal enquanto() loop reduzirá o espaço de pesquisa. Se o valor do índice baixo se tornar maior que o índice alto, então o espaço de busca foi esgotado, então o valor não pode estar presente.
enquanto (baixo <= alto) {
/* continuou... [1] */
}
retornar-1;
Depois de atualizar o ponto médio no início do loop, existem três resultados possíveis:
- Se o valor no ponto médio for o que estamos procurando, retorne esse índice.
- Se o valor do ponto médio for maior do que o que estamos procurando, reduza o valor máximo.
- Se o valor do ponto médio for menor, aumente o mínimo.
/* [1] ...continua */
médio = (baixo + (alto - baixo)) / 2;
if (arr[mid] == search_number)
retornar meio;
outrose (arr[mid] > search_number)
alto = médio - 1;
outro
baixo = médio + 1;
Teste a função com a entrada do usuário. Usar scanf() para obter entrada da linha de comando, incluindo o tamanho da matriz, seu conteúdo e um número para pesquisar:
intprincipal(){
int arr[100], i, arr_size, search_number;
printf("Digite o número de elementos: ");
scanf("%d", &arr_size);
printf("Por favor, insira os números: ");para (i = 0; eu < arr_size; i++) {
scanf("%d", &arr[i]);
}printf("Digite o número a ser pesquisado: ");
scanf("%d", &pesquisar_número);i = binarySearch (arr, arr_size, search_number);
se (i==-1)
printf("Número ausente");
outro
printf("O número está presente na posição %d", i + 1);
retornar0;
}
Se você encontrar o número, exiba sua posição ou índice, caso contrário, uma mensagem informando que o número não está presente.
Pesquisa Binária Usando C++
Você pode converter o programa C em um programa C++ importando o Fluxo de entrada e saída e usar namespace std para evitar repeti-lo várias vezes ao longo do programa.
#incluir <iostream>
usando namespacestd;Usar cout com operador de extração << em vez de printf() e cin com operador de inserção >> em vez de scanf() e seu programa C++ está pronto.
printf("Digite o número de elementos: ");
cout <<"Digite o número de elementos: ";
scanf("%d", &arr_size);
cin >> arr_size;Pesquisa binária usando Python
Como o Python não possui suporte embutido para arrays, use listas. Defina uma função, binarySearch(), que aceita três parâmetros, a lista, seu tamanho e um número para pesquisar:
defbusca binária(arr, arr_size, search_number):
baixo = 0
alto = arr_size - 1
enquanto baixo <= alto:
médio = baixo + (alto-baixo)//2
if arr[mid] == search_number:
retornar meio
elif arr[mid] > search_number:
alto = médio - 1
outro:
baixo = médio + 1
retornar-1Inicialize duas variáveis, baixo e alto, para servir como o limite inferior e superior da lista. Semelhante à implementação C, use um enquanto loop que restringe o espaço de pesquisa. Inicializar meio para armazenar o valor do meio da lista. Python fornece o operador de divisão de piso (//) que fornece o maior número inteiro possível.
Faça as comparações e reduza o espaço de pesquisa até que o valor médio seja igual ao número de pesquisa. Se o número de pesquisa não estiver presente, o controle retornará -1.
arr_size = int (input("Digite o número de elementos: "))
arr=[]
imprimir("Por favor, insira os números: ", fim="")
para i no intervalo (0,arr_size):
arr.apêndice(int(entrada()))
search_number = int (input("Digite o número a ser pesquisado: "))
resultado = binarySearch (arr, arr_size, search_number)
se resultado == -1:
imprimir("Número ausente")
outro:
print("Número é presente na posição ", (resultado + 1))Teste a função com a entrada do usuário. Usar entrada() para obter o tamanho da lista, seu conteúdo e um número para pesquisar. Usar int() para typecast a entrada de string aceita pelo Python como padrão em um inteiro. Para adicionar números à lista, use o acrescentar() função.
Chamar binarySearch() e passar os argumentos. Se você encontrar o número, exiba sua posição ou índice, caso contrário, uma mensagem informando que o número não está presente.
Saída do Algoritmo de Pesquisa Binária
A seguir está a saída do algoritmo de busca binária quando o elemento está presente na matriz:
A seguir está a saída do algoritmo de busca binária quando o elemento não está presente na matriz:
Aprenda as estruturas e algoritmos de dados fundamentais
A pesquisa é um dos primeiros algoritmos que você aprende e costuma ser solicitado em concursos de codificação, colocações e entrevistas. Alguns outros algoritmos que você deve aprender são classificação, hashing, programação dinâmica, correspondência de strings e algoritmos de teste de primalidade.
Além disso, é essencial entender a complexidade de tempo e espaço dos algoritmos. Eles são um dos conceitos mais cruciais na Ciência da Computação para determinar a eficiência de qualquer algoritmo. Com conhecimento de Estruturas de Dados e Algoritmos, você certamente construirá os melhores programas.
