activeinfo
 

Curso de Lógica da Programação na Prática.

Pesquisa Binária.

A pesquisa binária é mais inteligente que a pesquisa sequencial.

Para utilizar a pesquisa binária é necessário que o vetor esteja ordenado.

A pesquisa binária é mais eficiente e tem menor custo de processamento que a pesquisa sequencial. No entanto, a ordenação do vetor também tem seu custo.

Vejamos como funciona em um fluxograma:

Fluxograma

E o algoritmo:

var
  vetor: vetnum[0..3] de inteiro;
  elemento, posicao, primeiro, meio, ultimo: inteiro;
  achou: lógico;
inicio
  vetnum <- [8, 10, 20, 21];
  escreva 'Digite o elemento que deseja encontrar';
  leia elemento;
  achou <- falso;
  primeiro <- 0;
  meio <- 0;
  ultimo <- vetnum.tamanho – 1;
  enquanto primeiro <= ultimo e achou = falso
    meio <- (primeiro + ultimo) / 2;
    se elemento = vetnum[meio]
      achou <- verdadeiro;
      posicao <- meio + 1;
    senao se elemento < vetnum[meio]
      ultimo <- meio – 1;
    senao
      primeiro <- meio + 1;
    fimse
  fimenquanto
  se achou == verdadeiro
    escreva 'O elemento foi encontrado na ' + posicao + 'ª posição do vetor.';
  senao
    escreva 'O elemento não foi encontrado.';
  fimse
end

Vamos analisar o algoritmo acima:

Para ficar mais claro, vamos a uma ilustração da pesquisa binária em um vetor com 10 posições:

Pesquisa Binária em Ruby

Que tal experimentar um script em Ruby que utiliza pesquisa binária? Vamos lá:

#########################################################
# Programa: pesquisa_binaria.rb
#
# Descrição: Programa que demonstra a utilização de
#            pesquisa_binaria para buscar por um elemento
#            em um array
#
# Execução:
# ruby pesquisa_binaria.rb
#
# Autor: Marcos Cesar Kossoski
#
#########################################################
vet_num = [8, 10, 20, 21, 25, 30, 35, 50, 60, 80]
achou = false
puts 'Digite o elemento que deseja procurar.'
elemento = gets.chomp
elemento = elemento.to_i
inicio = 0
meio = 0
fim = vet_num.length - 1
while inicio <= fim and achou == false
  meio = (inicio + fim) / 2
  if elemento == vet_num[meio]
    achou = true
    posicao = meio + 1
  elsif elemento < vet_num[meio]
    fim = meio - 1
  else
    inicio = meio + 1
  end
end
if achou == true
  puts 'O elemento foi encontrado na ' + posicao.to_s + 'ª posição do vetor.'
else
  puts 'O elemento não foi encontrado.'
end

Testando o programa vemos que funciona adequadamente:

Testando Pesquisa Binária

Pesquisa Binária em Java

Vejamos uma implementação do algoritmo de pesquisa binária em Java:

/**********************************************************
 * Programa: programa em Java que demonstra a utilização
 *           do método de pesquisa binária para buscar
 *           por um elemento em um array
 *
 * Compilação: javac PesquisaBinaria.java
 * Execução: java PesquisaSequencial
 *
 * % java PesquisaBinaria
 * % Digite o número para procurar:
 * % 20
 * % O número foi encontrado na 3ª posição do array.
 * % java PesquisaSequencial
 * % 11
 * % O número não foi encontrado
 *
 * @author Marcos Cesar Kossoski
 *
**********************************************************/
import java.util.Scanner;
import java.util.regex.*;
public class PesquisaBinaria {

  public static void main (String[] args) {

    int[] vetNum = {8, 10, 20, 21, 25, 30, 35, 50, 60, 80};

    System.out.println("Digite o número para procurar: ");
    Scanner numero = new Scanner(System.in);
    String num = numero.nextLine();

    Pattern padrao = Pattern.compile("^([0-9]+)$");
    Matcher resultado = padrao.matcher(num);

    if (resultado.matches() == true) {
      int elemento = Integer.parseInt(num);
      int primeiro = 0;
      int meio = 0;
      int ultimo = vetNum.length - 1;
      int posicao = 0;
      boolean achou = false;
      while (primeiro <= ultimo && achou == false) {
        meio = (primeiro + ultimo) / 2;
        if (elemento == vetNum[meio]) {
          achou = true;
          posicao = meio + 1;
        } else if (elemento < vetNum[meio]) {
          ultimo = meio - 1;
        } else {
          primeiro = meio + 1;
        }
      }
      if (achou == true) {
        System.out.println("O número foi encontrado na " + posicao + "ª posição do array.");
      } else {
        System.out.println("O número não foi encontrado.");
      }
    } else {
      System.out.println("Digite um número inteiro válido.");
    }

  }
}

Compilando e rodando o programa, vemos que funciona tanto com números existentes no array quanto com inexistentes:

Pesquisa Binária em Array em Java

Pesquisa Binária em Javascript

No link abaixo você pode ver uma implementação do método de pesquisa binária em Javascript:

Pesquisa Binária em Javascript

Nosso próximo alvo de estudo são vetores com mais de uma dimensão: os vetores bidimensionais.

Voltar Próximo: Matrizes.