Pesquisa Ternária em um vetor ordenado
O algoritimo de pesquisa binária divide o vetor sucessivamente em duas partes, e utiliza a mesma
lógica porém dividindo o vetor em 3 partes.
lógica porém dividindo o vetor em 3 partes.
Descrição
O algoritimo de pesquisa binária divide o vetor sucessivamente em duas partes, e utiliza a mesma
lógica porém dividindo o vetor em 3 partes.
lógica porém dividindo o vetor em 3 partes.
/**
* Divide um vetor em 3 partes sucessivamente em busca de um elemento
* Retorna -1 caso o elemento não exista no vetor, ou o indice do elemento
* @param x
* @return
*/
public int pesquisaTer(int x){
int meio1, meio2;
int esq = 0;
int dir = arranjo.length-1;
do{
//Calcula a primeira parte do vetor evitando estrapolação
meio1=(dir - esq)/3 + esq;
//Calcula a segunda parte do vetor evitando que
meio2=((dir-esq)/3)*2 + esq;
//Caso o arranjo esteja em um dos meios encerra o metodo e retorna a posição
if(x==arranjo[meio1])
return meio1;
if(x==arranjo[meio2])
return meio2;
//Atualiza os indices esq e dir caso nao seja encontrado o elemento
if(x<arranjo[meio1]){
dir=meio1-1;
}
if (x>arranjo[meio1] && x< arranjo[meio2]){
esq=meio1+1;
dir=meio2 -1;
}
else if(x>arranjo[meio2]){
esq=meio2+1;
}
}while(esq<=dir);
return -1;
}