Eficiência

Procure pelo algortimo dos métodos quicksort e mergesort. Me parece que o mergesort é o mais rápido, mais não sei como é sua implementação. O quick é um pouco mais lento, mas estou certo que vc vai encontrar o algoritmo dele na internet. Blz! :thumbup:

Mas o array de entrada já está ordenado, ela só quer achar o subintervalo. Eu também acho que duas buscas binárias são suficientes e eficientes para o caso dela.

Eu concordo com o Thingol.

No java, existe o método Arrays.binarySearch, que pode ser usado no lugar de seus whiles.

Outra coisa, esteja sempre preparada para o caso dos elementos passados como parâmetro não existirem. Nesse caso lance alguma exceção do tipo IllegalArgumentException ou ArrayIndexOutOfBoundsException.

Parece que no Java 6 tem umas collections que já trabalham com “ranges”. Eu acho que vi isso num pdf do Luca, de uma palestra que ele ministrou certa feita…

Isso depende dos casos… o tipo de entrada faz a diferença no pior e melhor caso de cada algoritmo de ordenação…

:idea:

Se você tiver um histograma do array, ou sober que os valores são distribuidos de maneira uniforme, pode usar busca por interpolação, o pior caso dela é da mesma ordem que a busca-binária, porém o caso comum é muito melhor.

Foi mal gente, faltou de atenção pra responder :oops: .

Então, li novamente sobre o Java 6, e lá agora tem uma interface chamada NavigableSet que extend SortedSet. A classe TreeSet agora implementa esta NavigableSet.
Esta nova interface tem um método assim:

NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {...}
Ele parece que já faz todo o trabalho de que você tá preisando, Telma.
Ainda naum testei (To só com Java 5 na minha máquina) mas acho que isso aqui resolveria o problema:

public class Teste {
	public static void main(String[] args) {
		System.out.println(
			countInterval(new Integer[] {1,2,4,6,7,9}, 2, 8)
		);
	}
	
	public static int countInterval(Integer[] arr, int a, int b) {
		TreeSet<Integer> set = new TreeSet<Integer>(
			Arrays.asList(arr)
		);
		return set.subSet(a, true, b, true).size();
	}
}

Testem aí e vejam se dá certo, ok?

[color=darkblue][size=18]NOTAS DE EDIÇÃO[/size]:
:arrow: De fato, funciona mesmo o código acima. Acabo de testá-lo no meu recém instalado Mustang. Agora, não sei como é a performance dessa bagaça, teria que dar uma lida no javadoc da classe TreeSet ou então der uma olhada no código fonte.
:arrow: Infelizmente, teremos que fuçar o código fonte pra descobrir o algoritmo utilizado na classe TreeSet, uma vez que a documentação deste método no javadoc do Mustang simplesmente copia a especificação dste método lá da interface NavigableSet.
[/color]

Nota de edição foi boa… heheheheheh!!! :lol:

Muito obrigada a todos… eu realmente não posso usar coisas já feitas… tenho que ser eu a implementar, pois isto é para a faculdade. Mas deu para ter uma ideia…

obrigadão !!