Pesquisa de Dados - Binária

[0, 1, 2, 4, 5, 6, 7, 8, 9]

package pesquisa.binaria;

/**
 * Classe utilizada para demonstrar o algoritmo Pesquisa Binaria.
 */
public class PesquisaBinaria {
  public static void main(String[] args) {
    PesquisaBinaria bin = new PesquisaBinaria();
    
    int[] numeros = {1, 3, 4, 7, 9, 10, 13, 18, 20, 21, 22};
    
    bin.pesquisarNumero(20, numeros);
    bin.pesquisarNumero(3, numeros);
  }
  
  /**
   * Método que pesquisa um número dentro de um vetor de números.
   * Este método utiliza o algoritmo de pesquisa binaria.
   * 
   * @param x    - Número que será pesquisado.
   * @param numeros - Vetor de números.
   */
  public void pesquisarNumero(int x, int[] numeros) {
    int inicio = 0;         //Posição inicial do vetor.
    int meio = 0;          //Posição do meio do vetor.
    int fim = numeros.length - 1;  //Posição final do vetor.
    
    /* Enquanto a posição do inicio for menor ou igual a posição do fim,
      procura o valor de x dentro do vetor. */
    while(inicio <= fim) {
      meio = (fim + inicio) / 2; //Encontra o meio do vetor.
      
      System.out.println("Inicio: " + numeros[inicio] + " - Meio: " + numeros[meio] + " - Fim: " + numeros[fim]);
      System.out.println("Inicio: " + inicio + " - Meio: " + meio + " - Fim: " + fim);
      
      /* Se o valor que está no meio do vetor é igual ao valor procurado, 
        imprime que encontrou o valor e para de pesquisar. */
      if(numeros[meio] == x) {
        System.out.println("Encontrou o número " + x);
        break;
      }
      
      /* Este if serve para diminuir o tamanho do vetor pela métade. */
      /* Se o valor que está no meio do vetor for menor que o valor de x, 
        então o inicio do vetor será igual a posição do meio + 1. */
      if(numeros[meio] < x) {
        inicio = meio + 1;
      } else {
        /* Se o valor que está no meio do vetor for maior que o valor de x, 
          então o fim do vetor será igual a posição do meio - 1. */
        fim = meio - 1;
      }
    }
    
    /* Caso não encontre o valor pesquisado dentro do vetor,
      imprime que não encontrou o valor pesquisado. */
    if(inicio > fim) {
      System.out.println("Não encontrou o número " + x);
    }
  }
}

package pesquisa.binaria;

/**
 * Exemplo de uso do algoritmo Pesquisa Binaria, para pesquisar nomes
 * dentro de um intervalo de caracteres iniciais.
 */
public class PesquisarNomes {
  public static void main(String[] args) {
    PesquisarNomes pesquisarNomes = new PesquisarNomes();
    
    Pessoa ana = new Pessoa("Ana", 18);
    Pessoa carla = new Pessoa("Carla", 20);
    Pessoa felipe = new Pessoa("Felipe", 24);
    Pessoa patricia = new Pessoa("Patricia", 23);
    Pessoa rafael = new Pessoa("Rafael", 20);
    
    Pessoa[] pessoas = {ana, carla, felipe, patricia, rafael};
    
    int inicio = pesquisarNomes.pesquisar('A', pessoas);
    int fim = pesquisarNomes.pesquisar('F', pessoas);

    /* Imprime os nomes encontrados. */
    while(inicio >= 0 && inicio <= fim) {
      System.out.println(pessoas[inicio].getNome());
      inicio++;
    }
  }
}

  /**
   * Método utilizado para pesquisar uma pessoa que tem a primeira 
   * letra do nome igual a letra recebida.
   * Este método utiliza o algoritmo de pesquisa binaria.
   * 
   * @param letra  - Letra inicial do nome.
   * @param pessoas - Vetor de pessoas.
   * @return posição em que se encontra a pessoa com a letra pesquisada. Caso não
   * tenha nenhuma pessoa dentro do vetor com a letra igual a pesquisada, então 
   * retorna a posição mais proxima.
   */
  public int pesquisar(char letra, Pessoa[] pessoas) {
    int inicio = 0;         //Posição inicial do vetor.
    int meio = 0;          //Posição do meio do vetor.
    int fim = pessoas.length - 1;  //Posição final do vetor.
    
    /* Enquanto a posição do inicio for menor ou igual a posição do fim,
      procura o valor de x dentro do vetor. */
    while(inicio <= fim) {
      meio = (fim + inicio) / 2; //Encontra o meio do vetor.
      
      /* Se a primeira letra do nome da pessoa que está no meio do vetor for 
        igual a letra procurada, retorna o valor da posição do meio do vetor 
        e para de pesquisar. */
      if(pessoas[meio].getNome().charAt(0) == letra) {
        return meio;
      }
      
      /* Este if serve para diminuir o tamanho do vetor pela métade. */
      /* Se a primeira letra do nome da pessoa que está no meio do vetor for
        menor que o valor da letra procurada, então o inicio do vetor seráa 
        igual a posição do meio + 1. */
      if(pessoas[meio].getNome().charAt(0) < letra) {
        inicio = meio + 1;
      } else {
        /* Se a primeira letra do nome da pessoa que está no meio do vetor
          for maior que o valor da letra procurada, então o fim do vetor 
          será igual a posição do meio - 1. */
        fim = meio - 1;
      }
    }

    /* Se não encontrou nenhuma pessoa que tenha a primeira letra do nome 
      igual a letra que está sendo procurada, então retorna a posição do
      vetor que possui a letra mais proxima. */
    return fim;
  }