Fazer uma busca binaria invertida que faz a busca binária em vetores que estejam em ordem decrescente

26 de março de 2020 4 respostas

gab1 26 de março de 2020

Olá, preciso fazer um método de busca binária INVERTIDA, porém só consegui montar um código que faz busca binária normal, alguém pode me dar um help? Segue código:

public class BI {

public static int buscaBiInv (int v [], int proc){
	
	int inicio  = 0;
    int fim = v.length - 1;
    
    while(inicio <= fim)
      {
         int meio = (inicio + fim) / 2;
             
         if(v[meio] == proc)
            return meio;                          
         else
            if (v[meio] > proc)
               inicio = meio + 1;
            else
               fim = meio - 1;
      }
      return -1;
	
}
public static void main(String args[]) {
	
	int res5;
    int [] v ={9, 8, 5, 4, 3, 2, 0};
   	res5 = buscaBiInv (v, 2);
		System.out.println("O resultado da Busca Binaria Inversa e: " + res5);
	
}

}

4 Respostas

Jelson1 26 de mar. de 2020 1 like

A busca binária parte do pressuposto de que o vetor está ordenado, seja em ordem crescente ou decrescente, creio eu. Principalmente a busca binária que começa seu “chute” pelo meio do vertor. Então eu desconheço como seria essa busca binária invertida!
https://pt.khanacademy.org/computing/computer-science/algorithms/binary-search/a/implementing-binary-search-of-an-array

gab1 26 de mar. de 2020 1 like

Me expressei mal, desculpe. É uma busca binária inversa, começa das últimas posições e vem até as primeiras…

Jelson1 26 de mar. de 2020

Oi! Tem certeza que é uma busca binária o que você quer fazer? A busca binária não começa da última posição e vai até a primeira ou vice-versa. Ela começa no meio!

Definição do Wikipédia:

“A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop ) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor…”

O que você está descrevendo parece mais uma busca linear!

ever 1 de fev. de 2023

Se eu entendi, acho que ele deseja começar pelos estremos em direção ao meio, eu sugiro ele faça uso de alguma função lógica para isso um AND “&” e a função deslocamento “>>” pra rolar o Bit de rastreamento binário.

y=90;

x= y & x ;

If ( y == x )

y=>>y;

Criado 26 de março de 2020

Ultima resposta 1 de fev. de 2023

Respostas 4

Participantes 3

4 Respostas

Topicos relacionados