1. Tem-se um array de elementos possivelmente desordenados e distintos. Deseja-se encontrar a k-esima estatística de ordem desse array. Comente como você resolveria esse problema fazendo uso das ideias usadas no algoritmo do quicksort. Procure dar detalhes suficientes para deixar sua ideia completamente clara e detalhar o tempo de seu algoritmo (melhor e pior caso)
  2. O floor de um número x é o número menor que mais se aproxima de x. Considere um array ordenado e um número x (podendo pertencer ou não ao array). Implemente um algoritmo que busca o floor de x no array usando a estratégia de busca binária. O algoritmo deve ter a seguinte assinatura: int floor (int[] array, int x).

Passo 1

O enunciado tem duas partes. A primeira pede a k-ésima estatística de ordem (elemento de posto k) num array desordenado de elementos distintos, usando ideias do quicksort. A segunda pede um algoritmo que, dado um array ordenado e um valor x, retorne o índice do maior elemento do array que seja \le x (floor), usando busca binária.

Passo 2

Para o problema da k-ésima estatística de ordem usamos o algoritmo Quickselect, que se baseia no particionamento do quicksort:
1. Escolhemos um pivô (por exemplo, o elemento mediano de três ou de forma aleatória).
2. Particionamos o array em dois subarrays: valores < pivô e valores > pivô.
3. Se, após a partição, o pivô está na posição p:
  • Se p = k, então o pivô é a k-ésima estatística de ordem.
  • Se p > k, então recursamos na parte esquerda (índices < p).
  • Se p < k, então recursamos na parte direita, procurando o elemento de posto k-p-1 nesse subarray.

Passo 3

Analisando o tempo do Quickselect:
– Caso médio: cada partição divide “bem” o array (por exemplo, metade), e a recursão cai num subarray de tamanho \approx n/2. A recorrência é
T(n) = T\bigl(n/2\bigr) + O(n),
cuja solução é T(n)=O(n).
– Pior caso: o pivô é sempre o menor ou maior elemento, recursão em tamanho (n-1), e
T(n) = T(n-1) + O(n),
que dá T(n)=O(n^2).

Passo 4

Para implementar, basta escrever uma função recursiva Quickselect em que:
  • Se o array tem só um elemento, retorne-o.
  • Caso contrário, particione em relação ao pivô e recuse no lado certo de acordo com k.

Passo 5

Agora, para a função floor(int[] array, int x) fazemos uma busca binária modificada para achar o maior índice cujo valor seja \le x:
– Mantenha três variáveis: low\(=0\), hig\(h=a\)rray.length-\(1\) e result\(=\)-\(1\) (caso não haja floor).
– Enquanto low <\(=\) high:
1. Calcule mid \(=\) low \(+\) (high-low)/\(2\).
2. Se array[mid] \(==\) x, retorne mid imediatamente.
3. Se array[mid] < x, então result \(=\) mid e low \(=\) mid\(+1\).
4. Senão (array[mid] > x), faça high \(=\) mid-\(1\).
– Ao final do loop, result é o índice do floor (ou -\(1\) se todos os valores forem > x).

Passo 6

Pseudocódigo em Java:
int floor(int[] array, int x) {
    int low = 0;
    int high = array.length - 1;
    int result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (array[mid] == x) {
            return mid;
        } else if (array[mid] < x) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

Passo 7

A busca binária faz \log n comparações no pior caso, logo o tempo é O(\log n).

Resposta

1. Use Quickselect:
  • Caso médio O(n).
  • Pior caso O(n^2).
    2. A função floor acima retorna o índice do maior elemento \le x em tempo O(\log n).

Exercícios relacionados