Realizando busca em Array

Normalmente nos encontramos em uma situação onde temos um grupo de dados e desejamos verificar se existe um dado em particular neste conjunto. Este tipo de pesquisa é uma atividade corriqueira para programadores. Também não é incomum que estes dados estejam no formato de um array. Em Java, um Array é uma estrutura de dados que armazena elementos (números, strings, objetos) e infelizmente não possui um método para verificar se um elemento pertence a ele ou não. Este tipo de procedimento é encontrado em outras classes Java como em ArrayList e HashSet (são coleções Java).

Como fazemos então para buscar um elemento de um array?

Vou tentar esclarecer algumas formas de realizar busca em um array:

1) Realizar a busca convertendo o Array em um ArrayList
A classe ArrayList possui um método denominado contains() que retorna true se o objeto passado para ele estiver contido no ArrayList. Desta forma realizando a conversão com Array.asList() é possível realizar a busca.

2) Realizar a busca convertendo o Array em um HashSet
Da mesma forma que em ArrayList, podemos utilizar HashSet que apresenta o método contains(). Este método apresenta tempo de busca O(1), isto é, a busca tem tempo constante.

3) Realizar a busca utilizando Arrays.binarySearch()
A busca binária também é um método rápido de pesquisa mas os dados precisam estar ordenados, por isto temos que utilizar o método java.util.Arrays.sort() antes de fazer a busca. Precisamos notar que sort() ordena o próprio array e binarySearch() retorna a posição do array que foi encontrado ou um número negativo caso não tenha achado.

4) método da força bruta
Fazemos uma varredura nos elementos do array utilizam algum tipo de loop. NO nosso caso, preferi utilizar o foreach que provê um Iterator. A pesquisa é O(n) e por isto é o pior método dos relacionados acima.

Vamos ver nosso exemplo:

Veja que para imprimirmos o Array foi necessário convertê-lo em String. Isto foi facilmente realizado utilizando Arrays.toString().

Para converter o Array em uma lista também foi fácil. Bastou utilizar Arrays.asList(). E para conseguirmos o HashSet, converti o List do exemplo 1 utilizando HashSet<E>( List<E> ).

Para obtermos o array ordenado fiz um processo de duas etapas. Primeiro, copiei o array original para um novo array utilizando Arrays.copyOf( array, array.length). array.length está sendo utilizando para dizer a copyOf() que deve copiar todos os elementos. A etapa final foi ordenar que foi conseguido usando Arrays.sort(). Note que passamos como parâmetro o array a ser ordenado.

Tendo o array ordenado, a busca binária foi fácil.


A saída do programa é:

Ainda podemos utilizar a classe org.apache.commons.lang.ArrayUtils para realizar buscas em arrays. Podemos utilizar ArrayUtils.contains() e ArrayUtils.indexOf() para localizar um valor em arrays dos tipos primitivos do Java. Para que funcione é necessário que você baixe a biblioteca, inclua no seu arquivo .java com import e altere seu classpath para o local onde a biblioteca está.

Vamos alterar nosso programa um pouco para verificar esta opção também.

Criamos uma classe adicional com métodos estáticos para realizar o trabalho. Na classe original, adicionamos as chamadas para o exemplo 5 e 6.

Na primeira opção (exemplo 5) utilizei o ArrayUtils.contains() e no outro ArrayUtils.indexOf(). Notem que tive que realizar o import da classe para que o funcionasse e como estou no ambiente do NetBeans, acrescentei a biblioteca em um diretório denominado lib dentro do meu projeto: