Package br.unip.aps.busca

Class Buscas

java.lang.Object

br.unip.aps.busca.Buscas

public final class Buscas
extends Object

Busca sequencial e busca binaria (lowerBound/upperBound) sobre vetores, com contagem de operacoes.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final record	Buscas.Intervalo	Faixa de posicoes [inicio, fim) de um vetor ordenado.

Method Summary

Modifier and Type	Method	Description
static <T, K> int	contarLinear(T[] a, Function<? super T,? extends K> chave, Comparator<? super K> c, K de, K ate, OperationCounter k)	Busca sequencial do intervalo [de, ate]: examina todos os n elementos, ordenados ou nao.
static <T, K> int	contarLinearIgual(T[] a, Function<? super T,? extends K> chave, Comparator<? super K> c, K alvo, OperationCounter k)	Busca sequencial por igualdade.
static <T, K> Buscas.Intervalo	intervaloBinario(T[] a, Function<? super T,? extends K> chave, Comparator<? super K> c, K de, K ate, OperationCounter k)	Busca binaria do intervalo de chaves [de, ate]: duas buscas de O(log n).
static <T, K> int	lowerBound(T[] a, Function<? super T,? extends K> chave, Comparator<? super K> c, K alvo, OperationCounter k)	Primeira posicao cuja chave e maior ou igual ao alvo (vetor ordenado pela chave).
static <T, K> int	upperBound(T[] a, Function<? super T,? extends K> chave, Comparator<? super K> c, K alvo, OperationCounter k)	Primeira posicao cuja chave e estritamente maior que o alvo (vetor ordenado pela chave).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

lowerBound

public static <T,
K> int lowerBound(T[] a,
 Function<? super T,? extends K> chave,
 Comparator<? super K> c,
 K alvo,
 OperationCounter k)

Primeira posicao cuja chave e maior ou igual ao alvo (vetor ordenado pela chave).

upperBound

public static <T,
K> int upperBound(T[] a,
 Function<? super T,? extends K> chave,
 Comparator<? super K> c,
 K alvo,
 OperationCounter k)

Primeira posicao cuja chave e estritamente maior que o alvo (vetor ordenado pela chave).

intervaloBinario

public static <T,
K> Buscas.Intervalo intervaloBinario(T[] a,
 Function<? super T,? extends K> chave,
 Comparator<? super K> c,
 K de,
 K ate,
 OperationCounter k)

Busca binaria do intervalo de chaves [de, ate]: duas buscas de O(log n).

contarLinear

public static <T,
K> int contarLinear(T[] a,
 Function<? super T,? extends K> chave,
 Comparator<? super K> c,
 K de,
 K ate,
 OperationCounter k)

Busca sequencial do intervalo [de, ate]: examina todos os n elementos, ordenados ou nao.

contarLinearIgual

public static <T,
K> int contarLinearIgual(T[] a,
 Function<? super T,? extends K> chave,
 Comparator<? super K> c,
 K alvo,
 OperationCounter k)

Busca sequencial por igualdade.