Pessoal estou fazendo um programa, e preciso mediante o código abaixo retornar quantidade de comparações necessárias para a realização da busca, e também fazer uma busca de todos os elementos do vetor e apresentar média necessária de comparação na busca, o vetor é de 1000 posições.
// Classe que contém um array de inteiros aleatórios e um método
// que utiliza a pesquisa binária para localizar um inteiro.
import java.util.Random;
import java.util.Arrays;
public class BuscaBinaria
{
private int[] data; // array de valores
private static Random generator = new Random();
// cria um array de um dado tamanho e o preenche com inteiros aleatórios
public BuscaBinaria( int tamanho )
{
data = new int[ tamanho ]; // cria espaço para o array
// preenche o array com valore inteiros aleatórios no intervalo de 10-100
for ( int i = 0; i < tamanho; i++ )
data[ i ] = 10 + generator.nextInt( 90 );
Arrays.sort( data );
} // fim do construtor de BuscaBinaria
// realiza uma pesquisa binária nos dados
public int pesquisaBinaria( int pesquisaElemento )
{
int areaBaixa = 0; // extremidade baixa da área de pesquisa
int areaAlta = data.length - 1; // extremidade alta da área de pesquisa
int areaMedia = ( areaBaixa + areaAlta + 1 ) / 2; // elemento do meio
int local = -1; // valor retornado quando não localizado
do // faz um loop para busca do elemento
{
// imprime os elementos remanescentes do array
System.out.print( saidaElementos( areaBaixa, areaAlta ) );
// geração de espaços para alinhamento
for ( int i = 0; i < areaMedia; i++ )
System.out.print( " " );
System.out.println( " * " ); // indicará o meio atual
// caso o elemento for localizado no meio
if ( pesquisaElemento == data[ areaMedia ] )
local = areaMedia; // esta variável está recebendo o meio atual, ou seja, sua localização
// quando o valor do meio é muito alto
else if ( pesquisaElemento < data[ areaMedia ] )
areaAlta = areaMedia - 1; // eliminará a metade mais alta
else // quando o valor do meio é muito baixo
areaBaixa = areaMedia + 1; // eliminará a metade mais baixa
areaMedia = ( areaBaixa + areaAlta + 1 ) / 2; // executa o recálculo do meio
} while ( ( areaBaixa <= areaAlta ) && ( local == -1 ) );
return local; // irá retornar a localização da chave de busca
} // fim do método BuscaBinaria
// este método irá gerar a saída de determinados valores no array
public String saidaElementos( int elemento1, int elemento2 )
{
StringBuffer analise = new StringBuffer();
// irá gerar espaços para alinhamento
for ( int i = 0; i < elemento1; i++ )
analise.append( " " );
// gera a saída dos elementos que irão continuar no array
for ( int i = elemento1; i <= elemento2; i++ )
analise.append( data[ i ] + " " );
analise.append( "\n" );
return analise.toString();
} // fim do método saidaElementos
// este método gera saída de valores no array
public String toString()
{
return saidaElementos( 0, data.length - 1 );
} // fim do método toString
} // fim do método BuscaBinária
// esta classe ChamadaBinaria irá utilizar a pesquisa binária para localizar um valor no array.
//import java.util.Scanner;
import java.util.*;
public class ChamadaBinaria
{
public static void main( String args[] )
{
// Está sendo criado um objeto Scanner para que seja possível inserção de dados
Scanner entradaValor = new Scanner( System.in );
int leituraInteiro; // Variável utilizada como chave de pesquisa
int posicaoElemento; // Variável para localização da chave de pesquisa no array
int compara=0;
// Está sendo criado e gerado um saída do Array
BuscaBinaria criaElemento = new BuscaBinaria( 10 );
System.out.println( criaElemento );
// Está lendo o valor de busca do usuário
System.out.print(
"Entre com um número INTEIRO ou (digite -1 para encerrar o programa): " );
leituraInteiro = entradaValor.nextInt(); //Entrada do usuário para pesquisa ou para finalizar
// o programa caso desejar !!!!
System.out.println();
// insere repetidamente um inteiro; -1 encerra o programa
while ( leituraInteiro != -1 )
{
// irá utilizar a pesquisa binária na tentativa den encontrar o inteiro informado pelo
// usuário
posicaoElemento = criaElemento.pesquisaBinaria( leituraInteiro );
// Irá entrar nesta condição quando o valor inteiro não é localizado
if ( posicaoElemento == -1 )
System.out.println( "O Valor INTEIRO informado " + leituraInteiro +
" não foi localizado.\n" );
else // Entrará nesta condição quando o valor inteiro foi localizado, retornando também
// para o usuário a posição em que ele se encontra.
System.out.println( "O valor INTEIRO informado " + leituraInteiro +
" foi encontrado e está na posicao " + posicaoElemento + ".\n" );
int resultado = (int) Math.pow(2,10)-1;
int resultado2 = resultado/2;
System.out.println("Quantidade de comparações necessárias é "+ resultado);
System.out.println("Média de comparação necessária: "+ resultado2);
// obtém nova entrada do usuário ou opção para encerrar o programa se desejar
System.out.print(
"Entre com um valor para ser consultado ou (digite -1 para encerrar o programa): " );
leituraInteiro = entradaValor.nextInt(); // lê um int do usuário
System.out.println();
} // fim do while
} // fim de main
} // fim da classe ChamadaBinaria