Implementacao-de-Algoritmos-de-Busca-Linear-e-Binaria-em-Java

package atividade01 Interface para implementação da classe Busca Os métodos booleanos devem retornar false se k não estiver no vetor numeros public interface BuscaIF int geraVetorNumericoOrdenadoint tamanho boolean buscaLineariterativaint numeros int k boolean buscaLinearrecursivaint numeros int k boolean buscaBinariaiterativaint numeros int k boolean buscaBinariarecursivaint numeros int k public class BrincandoComBusca public static void mainString args BuscaIF b new Busca final int numeroParaBuscar 1 final int vetor1000 bgeraVetorNumericoOrdenado1000 long antes depois antes SystemnanoTime bbuscaLineariterativavetor1000 numeroParaBuscar depois SystemnanoTime SystemoutprintlnbuscaLineariterativa depoisantes antes SystemnanoTime bbuscaLinearrecursivavetor1000 numeroParaBuscar depois SystemnanoTime SystemoutprintlnbuscaLinearrecursiva depoisantes antes SystemnanoTime bbuscaBinariaiterativavetor1000 numeroParaBuscar depois SystemnanoTime SystemoutprintlnbuscaBinariaiterativa depoisantes antes SystemnanoTime bbuscaBinariarecursivavetor1000 numeroParaBuscar depois SystemnanoTime SystemoutprintlnbuscaBinariarecursiva depoisantes Atividade 01 7 Data de entrega 2359 Item postado em 21 de mar Atribuído Atividade iniciada na aula do dia 2103 A atividade pode ser realizada em trio Devese seguir as diretrizes comentadas na aula criando as classes BrincandoComBuscajava que deve conter o main e Buscajava que deve seguir a interface BuscaIF Anexar via classroom um arquivo pdf 1 página analisando o que foi feito e os resultados obtidos e o pacote atividade01 com os três arquivos java apenas um integrante deve anexar indicando os nomes dos integrantes como comentário particular As entregas que não seguirem as diretrizes são passíveis de nota zero Prazo de reposição 24 horas após o prazo regular após tal horário nota zero Lembrete só é possível repor uma atividade por unidade Ver atividade Atividade 00 LEDA Sem data de entrega Existem várias formas de se realizar a busca de um elemento em uma estrutura de dados sendo as mais comuns as buscas lineares e binárias Neste texto vamos abordar os códigos de busca linear iterativo busca linear recursiva busca binária iterativa e busca binária recursiva O código de busca linear iterativo é uma busca simples que percorre a estrutura de dados de forma sequencial comparando o elemento buscado com cada elemento da estrutura Caso o elemento seja encontrado a busca é encerrada e é retornado o índice do elemento Caso contrário a busca continua até o final da estrutura quando é retornado o valor 1 indicando que o elemento não foi encontrado O código de busca linear recursiva utiliza a mesma lógica de busca sequencial porém de forma recursiva A função de busca recebe a estrutura de dados e o elemento a ser buscado como parâmetros Em seguida é comparado o primeiro elemento da estrutura com o elemento buscado Caso sejam iguais a função retorna o índice do elemento Caso contrário a função é chamada recursivamente passando a estrutura de dados sem o primeiro elemento Caso a estrutura esteja vazia e o elemento não tenha sido encontrado é retornado o valor 1 O código de busca binária iterativa é uma busca mais eficiente que a busca linear mas requer que a estrutura de dados esteja ordenada A busca é realizada através da comparação do elemento buscado com o elemento central da estrutura Caso o elemento central seja igual ao elemento buscado é retornado o índice do elemento Caso contrário se o elemento central for menor que o elemento buscado a busca é realizada na metade superior da estrutura descartando a metade inferior Se o elemento central for maior que o elemento buscado a busca é realizada na metade inferior da estrutura descartando a metade superior Esse processo é repetido até que o elemento seja encontrado ou a estrutura seja reduzida a uma única posição quando é retornado o valor 1 indicando que o elemento não foi encontrado O código de busca binária recursiva segue a mesma lógica do código iterativo porém de forma recursiva A função de busca recebe a estrutura de dados o elemento a ser buscado o índice inicial e o índice final como parâmetros A cada chamada recursiva é calculado o índice central da estrutura e comparado com o elemento buscado Caso sejam iguais é retornado o índice do elemento Caso contrário se o elemento central for menor que o elemento buscado a função é chamada recursivamente passando o índice central mais 1 como índice inicial e o índice final como índice final Se o elemento central for maior que o elemento buscado a função é chamada recursivamente passando o índice inicial como índice inicial e o índice central menos 1 como índice final Esse processo é repetido até que o elemento seja encontrado ou a estrutura seja reduzida a uma única posição quando é retornado o valor 1 Todas essas implementações podem ser realizadas utilizando uma interface comum de busca que define os métodos a serem implementados Os benefícios de se utilizar uma interface comum são a padron O código acima recebe uma lista e um valor a ser buscado nessa lista e retorna o índice do valor na lista se encontrado Caso contrário retorna 1 A busca é realizada de forma iterativa percorrendo cada elemento da lista até encontrar o valor desejado ou percorrer toda a lista Para utilizar a função acima basta criar uma lista e chamar a função passando essa lista e o valor a ser buscado como argumentos lista 1 2 3 4 5 valor 3 indice buscalinearinterativolista valor if indice 1 printfO valor valor foi encontrado na posição indice da lista else printfO valor valor não foi encontrado na lista No exemplo acima a lista é 1 2 3 4 5 e o valor a ser buscado é 3 A função buscalinearinterativo é chamada passando esses valores como argumentos e o resultado é armazenado na variável indice Se o valor for encontrado na lista o índice é exibido na tela Caso contrário uma mensagem informando que o valor não foi encontrado é exibida