Pesquisa Binária - Parte 4: Uma pergunta de entrevista tramada

Para fechar este ciclo sobre a pesquisa binária, sugiro uma pergunta de entrevista:

Dados 2 arrays de inteiros ordenados de forma crescente, determina o K-ésimo número mais pequeno do conjunto dos 2 arrays em tempo sublinear e com O(1) de memória extra.

Em termos lúdicos, penso que é um bom exercício, mas, na minha opinião, esta é uma má pergunta para se colocar numa entrevista. De facto, é das piores que já vi em sites como o Glassdoor ou o CareerCup. No entanto, esta pergunta já foi colocada a um amigo meu numa entrevista, por isso convém estar preparado.

Há 2 razões fundamentais pelas quais penso que é uma má pergunta no contexto de uma entrevista:

1. Em termos conceptuais, a ideia base é +- óbvia e não há grandes alternativas de solução.
2. A dificuldade da pergunta prende-se mais com detalhes de implementação do que em pensar na melhor abordagem para o problema.

Voltando à pergunta, a restrição de memória impede-nos de fundir os 2 arrays num único array ordenado. De qualquer modo, esta fusão seria linear no número de elementos dos arrays, violando a restrição de tempo sublinear.

Pesquisas e arrays ordenados soa a pesquisa binária, não há muitas voltas a dar. A diferença neste caso é que vamos pesquisar nos 2 arrays A e B ao mesmo tempo. Assim, vamos ter um ponto médio para cada array.
Enquanto não esgotarmos um dos arrays (o apontador da esquerda não excede o da direita), basta verificarmos a quantidade de elementos menores ou iguais aos pontos médios.
Se esta quantidade exceder K, significa que o número pretendido não pode estar para a direita do ponto médio do array cujo valor no ponto médio é maior. Exemplo:

A = [1, 2, 7, 9] , B = [3, 4, 5, 6, 8] , K = 4
esq_a = 0, dir_a = 3, mid_a = 1, a[mid_a] = 2
esq_b = 0, dir_b = 4, mid_b = 2, b[mid_b] = 5

Número de elementos até aos pontos médios é (mid_a+1) + (mid_b+1) = 5
Como 5 > K, podemos descartar todos os números à direita do mid_b porque é 
garantido que todos os números até ao ponto médio do array A são menores ou 
iguais que os valores para a direita do ponto médio do array B.

De modo análogo, se a quantidade não exceder K, então podemos descartar a metade inferior do array com números mais pequenos até ao seu ponto médio. A parte má numa entrevista é escrever o código sem bugs sem poder testar.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

int KesimoArraysOrdenados(int* a, int na, int* b, int nb, int k) { int esq_a = 0, mid_a, dir_a = na-1, esq_b = 0, mid_b, dir_b = nb - 1; while (esq_a <= dir_a && esq_b <= dir_b) { mid_a = (esq_a + dir_a) / 2; mid_b = (esq_b + dir_b) / 2; // Temos mais de K números até aos mids? (+2 para incluir os mids) if (mid_a + mid_b + 2 > k) { // Sim, vamos para a parte inferior do array com maior número médio if (a[mid_a] > b[mid_b]) { dir_a = mid_a - 1; } else { dir_b = mid_b - 1; } } else { // Não, vamos para a parte superior do array com menor número médio if (a[mid_a] < b[mid_b]) { esq_a = mid_a + 1; } else { esq_b = mid_b + 1; } } } // A resposta está no array cujo range não foi esgotado if (esq_a <= dir_a) { return a[k - esq_b - 1]; } else { return b[k - esq_a - 1]; } }

Em cada iteração, o range de um dos arrays é cortado para metade (superior ou inferior). No pior caso, um dos ranges tem só 1 elemento e o outro é esgotado. Assim, esta solução corre em tempo O(log(na) + log(nb)).