Eficiência

2 de março de 2007 6 respostas

TelmaSofiaPJ 2 de março de 2007

aloha…

Eu tenho que implementar um método que conta o número de elementos de um array ordenado que se encontram no intervalo [b,c]. Por exemplo, o array [1,2,4,6,7,9] e o intervalo [2,8], o método retorna 4 . Mas preciso de o algoritmo o mais eficiente possível.
Eu fiz o seguinte :

public static int countInterval(int[]a,int b,int c){
		int i=a.length/2;
		int j=i;
		
		while(i>=0 && i<a.length){
			
			if(a[i]==b || (a[i+1]>b && a[i-1]<b)) break;
			else{
				if(a[i]>b){i=i/2;continue;}
				if(a[i]<b){i+=i/2;continue;}
			}
			
		}
		while(j>=0 && j<a.length){
			if(a[j]==c|| (a[j+1]>c && a[j-1]<c))break;
			else{
				if(a[j]>c){j=j/2; continue;}
				if(a[j]<c){j+=j/2; continue;}
			}
		}
		
		return j-i+1;
		
	}

Utilizando duas pesquisas binárias, penso que seja o mais eficiente…

Haverá alguma maneira mais eficiente de fazer isto ???

6 Respostas

sergiotabordaPJ 2 de mar. de 2007

public int count(int[] array , int a, int b ){

 if (a==b){
return 0;
} else if (a>b){
   throw new IllegalArgumentException("o inicio do intervalo é maior que o fim")
}
 Arrays.sort(array) // necessário apenas se array não está ordenado.

// supoe-se que a < b 
 int ka = Arrays.binarySearch(array,a);
 int kb = Arrays.binarySearch(array,b);
 
 // obtém posições onde o numero foi encontrado,ou deveria ser
 ka = ka <0 ?  Math.abs(ka)-1:ka;
 kb= kb <0 ?  Math.abs(kb)-1:kb;

 return kb-ka;

}

ChristielenPJ 2 de mar. de 2007

Tem que ser pesquisa binária?

sergiotabordaPJ 2 de mar. de 2007

Porque não pode ser ?

TelmaSofiaPJ 2 de mar. de 2007

Tem que ser o mais eficiente possível… iterativo não é tão eficiente né ??

Mas tem alguma outra ideia ?

sergiotabordaPJ 2 de mar. de 2007

“TelmaSofia”:
Tem que ser o mais eficiente possível… iterativo não é tão eficiente né ??

Mas tem alguma outra ideia ?

Não entendi muito bem as suas perguntas.
Ierativo nem sempre é o mais eficiente, pode ser o mais simples de entender e/ou implementar e acaba funcionando, mas normalmente não é o mais eficiente. Outra ideia ?! Essa não serve ? :roll:

ChristielenPJ 5 de mar. de 2007

public class Teste {
	
	public static int countInterval(int[]a,int b,int c){
		int numero = 0;
		for(int i=0; i < a.length; i++){
			if((a[i] >= 2) && (a[i] < 8 )){
				numero++;
			}
		}
		
		return numero;
	}

	public static void main(String[] args) {
		int[] array = {1,2,4,6,7,9};
		int numero = Teste.countInterval(array, 2, 8);
		System.out.println(numero);
	}
}

Criado 2 de março de 2007

Ultima resposta 5 de mar. de 2007

Respostas 6

Participantes 3

6 Respostas

Topicos relacionados