O algoritmo de Busca Linear e o Java
Neste artigo vou falar sobre o algoritmo de Busca linear e a evolução do Java na sua execução. O algoritmo de Busca Linear é um algoritmo simples, que faz a pesquisa por um elemento em um vetor (array ou lista) desordenado, de modo sequencial.
Visão do acesso sequencial do vetor
Os elementos de um vetor são identificados por meio de índices. (índice = posição no vetor)
Visão índices e elementos do vetor
O primeiro elemento tem o índice 0 (zero). Portanto, para um vetor de n elementos, os índices variam de 0 a n-1., acima vemos um vetor numérico de 11 elementos, mas poderia ser qualquer outro tipo de dado como letras, símbolos e etc..
Algoritmo de Busca Linear
Passos:
“dado um vetor de números (inteiros) desordenado”
“dado um número a ser buscado no vetor”
“para cada posição do vetor”
“comparar se, o elemento na posição atual do vetor, é igual ao numero buscado”
“se, o numero na posição do vetor for igual ao número buscado”
“o algoritmo termina e imprime o índice do numero encontrado”
“caso contrario, a cada loop, a busca continua para a próxima posição do array”
“se todo array foi percorrido e o numero não encontrado, imprima -1”
Em Portugol:
Entrada:
Vetor de números (inteiros) desordenado.
Um número a ser buscado.
Saída:
Se encontrou o número no vetor imprima o índice do número.
Se não encontrou o número imprima -1.
Inicio
| inteiro n; // tamanho do vetor;
| inteiro vetor[n];
| inteiro x;
|
| // i = índice do vetor
| para (inteiro i = 0; i < n; i ++)
| | se (vetor[i] == x )
| | |
| | | escreva (“Encontrado na posição:”, i);
| | fim se
| fim para
| // não encontrou
| escreva ( -1);
Fim
Fluxograma do algoritmo
Primeira abordagem
Usando a Força Bruta
Típico do algoritmo de Busca Linear a busca por força bruta é de fácil implementação. Entretanto, seu custo tende a crescer muito rápido, caso a pesquisa seja feita em um vetor muito grande. Em Java esse código é bastante simples, sendo utilizado um “for” para interação no vetor e um “if” para verificação do valor procurado. Veja o código abaixo:
public static int buscaLinear(int[] vetor, int numeroProcurado) {
int n= vetor.length; /* obtendo o tamanho do vetor*/
for (int i = 0; i < n; i++)
if (vetor[i] == numeroProcurado)
return i;
return –1; // Não achou numero procurado, retorna -1
}
Sendo esse algoritmo quanto a sua complexidade, um algoritmo O(n).
O(1) – melhor caso: o elemento buscado é o primeiro do array
O(N) – pior caso: o elemento buscado é o último do array ou não existe no array
O(N/2) – caso médio: o elemento é encontrado após (N+1)/2 comparações.
Segunda abordagem
Usando Hash Map
Usando um Hash Map em Java podemos melhorar a complexidade de tempo de execução, de uma maneira mais eficiente para verificar se um numero existe em um array.
Pois se o numero existe, precisamos retornar seu índice e em Java a melhor maneira de manter um mapeamento de cada elemento do vetor para seu índice é utilizando um Hash Map onde o que importa agora e o valor da sua chave para encontrar o numero buscado, e a chave pode ser: string, int, double, Object etc… no nosso caso será um numero.
O Hash Map esta presente no Java desde a versão 1.2, e tem recebido melhorias significativas de performance e sintaxe a cada nova versão do Java, é notório o uso massivo desse recurso em códigos Java.
O HashMap é uma implementação da interface Map e de forma simples de dizer, é que um conjunto de pares chave-valor (key, value) que tem o poder de se auto redimensionar dentre outras características importantes, que devem ser usadas com cautela.
Você pode aprender mais sobre HashMap lendo o artigo do RamsKrishna Joshi ou do Nashim Salmay e consultando as referências no final desse artigo. Com uso do HashMap reduzimos o tempo de pesquisa de O(n) para O(1) trocando espaço por velocidade.
Uma tabela Hash é construída exatamente para esse propósito, de suportar pesquisas rápidas em um tempo quase constante.
Uma implementação simples do algoritmo usando Hash Map usa uma interação “for“, onde adicionamos o valor de cada elemento e seu índice à tabela (Map) e só então verificamos com um “if” se o numero existe na tabela.
public static int buscaLinearComHashMapTwoPass(int[] vetor, int numeroProcurado) {
Map<Integer, Integer> map = new HashMap<>();
// passsando os dados do vetor pra um HasMap
for (int i = 0; i < vetor.length; i++) {
map.put(vetor[i], i);
}
// verificando se o numero procurado existe no hashMap
if (map.containsKey(numeroProcurado)) return map.get(numeroProcurado);
// se nao encontrado
return –1;
}
Terceira abordagem
Hash Map com uma iteração verificada
Acontece que podemos fazer isso em uma única iteração “for“. Enquanto iteramos inserimos e os elementos do vetor na tabela, também olhamos para verificar com um “if” se o numero procurado já existe na tabela. Se existir, o retornamos imediatamente.
public static int buscaLinearComHashMapOnePass(int[] vetor, int numeroProcurado) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < vetor.length; i++) {
// verifica se o numeroProcurado ja existe no HashMap
if (map.containsKey(numeroProcurado))
return map.get(numeroProcurado);
map.put(vetor[i], i); // passsando os dados do vetor pra um HasMap
}
// se nao encontrado
return -1;
}
Quarta abordagem
Utilizando Stream API
Streams API é um recurso que o Java traz a partir da versão 8, com novas classes e métodos que ajudam a manipular coleções (vetor, array, listas) de maneira mais simples e eficiente, usando o estilo de programação funcional. Que muda a forma como se escreve o código. Abaixo o algoritmo de Busca Linear escrito em Java usando a sintaxe das linguagens que seguem o paradigma funcional. IntStream é uma interface dessa API e tem suporte a operações de agregação sequenciais e paralelas, para encontrar um numero dentro do vetor (array ou lista). Veja código abaixo:
private static int buscaLinearStream(int[] vetor, int numeroProcurado) {
return IntStream.range(0, vetor.length) .filter(i -> vetor[i] == numeroProcurado)
.mapToObj(index -> index)
.findFirst()
.orElse(-1); // se nao encontrou retorna -1
}
Coleções como fontes de dados para Streams
Todas as coleções no Java podem ser fontes de dados para a Stream API
Manipulando numeros
int vetor[] = {1, 5, 9, 4, 8, 50, 30, 40, 78, 63, 47};
Convertendo vetor(array ou lista) para Streams
Stream stream1 = Stream.of(vetor) ou Stream stream1 = Arrays.stream(array)
Manipulando textos
Inclusive textos e frase podem ser facilmente manipuladas com Stream, transformndo uma string em uma Lista de String ou uma String em uma Lista de caracter, que como beneficio passam a herdar todos os métodos da interface List, tais como insert, search, remove, Iterator etc…Veja o código abaixo:
// Convertendo uma string em uma Lista de strings
// entrada: Udinei da Silva
// saida: [Udinei, da, silva]
public static List<String> split(String str){
return Stream.of(str.split(" "))
.map(elem -> new String(elem))
.collect(Collectors.toList());
}
// Convertendo uma string em uma Lista de strings
// entrada: Udinei da Silva
// saida: [Udinei, da, silva]
public static List<String> split(String str){
return Stream.of(str.split(” “))
.map(elem -> new String(elem))
.collect(Collectors.toList());
}
Conclusão
O algoritmo de Busca Linear é considerado um algoritmo simples e básico no mundo da programação, mas muito utilizado no dia a dia do desenvolvedor, e saber empregar diversas abordagens técnicas para resolver problemas com esse algoritmo é de suma importância.
Como podemos ver esse algoritmo pode ser abordado de diversas formas, e nesse artigo vimos que o Java traz consigo uma evolução na melhor forma de executar esse algoritmo, evoluindo desde as estruturas básicas de controles para estruturas de dados mais eficientes como HashMap, sendo a terceira abordagem aqui apresentada a mais eficiente, seguida do uso da Streams API.
A Stream API eleva o Java para outro nível de codificação, pois diminui a quantidade de código a ser escrito e absorve responsabilidades de controle de fluxos como while, for, do while etc, ficando somente as regras de negócio a única responsabilidade do desenvolvedor.
A evolução do Java com uso de Streams fornece técnicas sofisticadas de processamento de dados, e uma nova forma de escrever códigos Java, sinalizando uma forte tendência em Java, fazer uso dessa API para solucionar de forma simples e objetiva algoritmos como o de Busca Linear e outros algoritmos de grande complexidade tornando-os mais eficientes, no gerenciamento de memória (heap) e trabalhos de execução paralela.
Esse artigo é uma versão inspirada na solução do problema <b>TowSum</b> proposto pela LeetCode em seu [site](https://leetcode.com/problems/two-sum/solution/). A Leetcode é uma plataforma que ajuda você a aprimorar suas habilidades em programação.
Você pode conferir o código do artigo no meu gitHub.
Dúvidas ou sugestões, manda no meu email: [email protected]
Referências:
Algoritmos Teoria e Prática
HashMap
Força Bruta
Argumentação Big- O
Busca por Força Bruta
Streams API
InstStream
