Pesquisa binária

Instruções

A tua tarefa é implementar um algoritmo de pesquisa binária.

Um algoritmo de pesquisa binária encontra um elemento numa lista dividindo-a repetidamente ao meio e ficando apenas com a metade que contém o elemento que procuramos. Permite-nos reduzir rapidamente as possíveis localizações do nosso elemento até o encontrarmos, ou até eliminarmos todas as localizações possíveis.

O algoritmo funciona assim:

• Encontra o elemento do meio de uma lista ordenada e compara-o com o elemento que procuramos.
• Se o elemento do meio for o que procuramos, terminámos!
• Se o elemento do meio for maior do que o que procuramos, podemos eliminar esse elemento e todos os elementos a seguir a ele.
• Se o elemento do meio for menor do que o que procuramos, podemos eliminar esse elemento e todos os elementos antes dele.
• Se todos os elementos da lista tiverem sido eliminados, então o elemento não está na lista.
• Caso contrário, repete o processo na parte da lista que ainda não foi eliminada.

Eis um exemplo:

Digamos que procuramos o número 23 na seguinte lista ordenada: [4, 8, 12, 16, 23, 28, 32].

• Começamos por comparar o 23 com o elemento do meio, o 16.
• Como 23 é maior do que 16, podemos eliminar a metade esquerda da lista, ficando com [23, 28, 32].
• De seguida, comparamos o 23 com o novo elemento do meio, o 28.
• Como 23 é menor do que 28, podemos eliminar a metade direita da lista: [23].
• Encontrámos o nosso elemento.

Comportamento

A tua solução deve corresponder ao comportamento das funções searchsorted incorporadas na Julia para os casos de teste. Isto significa que, em vez de devolveres o índice do primeiro elemento correspondente que encontras na lista, vais devolver um intervalo cujo limite inferior é o índice do primeiro elemento correspondente na lista e cujo limite superior é o índice do último elemento correspondente na lista. No entanto, para simplificar a tua solução podes assumir que o elemento alvo não está repetido, exceto no conjunto de testes da tarefa bónus sobre correspondências múltiplas.

Se o elemento procurado não estiver na lista, tens de devolver um intervalo vazio cujo limite inferior é o índice no qual o elemento poderia ser inserido na lista ordenada. Um intervalo vazio é qualquer intervalo em que o limite superior seja inferior ao limite inferior.

Lê a documentação e os exemplos da função searchsorted para mais detalhes:

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.

See also: insorted, searchsortedfirst, sort, findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

Tarefas bónus

• Amplia a tua solução para suportar os argumentos nomeados by, lt e rev, de forma que by especifique uma transformação aplicada a todos os elementos da lista, lt especifique uma comparação e rev especifique se a lista está ordenada em ordem inversa. Quando usares estes parâmetros, tens de assumir que a lista já foi ordenada com eles. Consulta a documentação de sort para mais detalhes.
• Suporta listas em que o elemento alvo se repete (encontra o primeiro e o último índice a que o elemento alvo é igual).

---

Fonte

Wikipedia