Busca binária

Instruções

Sua tarefa é implementar um algoritmo de busca binária.

Um algoritmo de busca binária encontra um item em uma lista dividindo-a repetidamente ao meio e mantendo apenas a metade que contém o item que estamos procurando. Isso nos permite estreitar rapidamente as possíveis localizações do nosso item até encontrá-lo, ou até termos eliminado todas as localizações possíveis.

O algoritmo funciona assim:

• Encontre o elemento do meio de uma lista ordenada e compare-o com o item que estamos procurando.
• Se o elemento do meio for o nosso item, pronto, terminamos!
• Se o elemento do meio for maior que o nosso item, podemos eliminar esse elemento e todos os elementos depois dele.
• Se o elemento do meio for menor que o nosso item, podemos eliminar esse elemento e todos os elementos antes dele.
• Se todos os elementos da lista tiverem sido eliminados, então o item não está na lista.
• Caso contrário, repita o processo na parte da lista que não foi eliminada.

Veja um exemplo:

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

• Começamos comparando 23 com o elemento do meio, 16.
• Como 23 é maior que 16, podemos eliminar a metade esquerda da lista, ficando com [23, 28, 32].
• Em seguida, comparamos 23 com o novo elemento do meio, 28.
• Como 23 é menor que 28, podemos eliminar a metade direita da lista: [23].
• Encontramos o nosso item.

Comportamento

Sua solução deve corresponder ao comportamento das funções searchsorted nativas do Julia para os casos de teste. Isso significa que, em vez de retornar o índice do primeiro elemento correspondente que você encontrar na lista, você vai retornar um intervalo cujo limite inferior é o índice do primeiro elemento correspondente da lista e cujo limite superior é o índice do último elemento correspondente da lista. No entanto, para simplificar sua solução, você pode assumir que o elemento procurado não se repete, exceto no conjunto de testes da tarefa bônus sobre múltiplas correspondências.

Se o item procurado não estiver na lista, você deve retornar um intervalo vazio cujo limite inferior é o índice no qual o item poderia ser inserido na lista ordenada. Um intervalo vazio é qualquer intervalo em que o limite superior seja menor que o limite inferior.

Leia 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

• Amplie sua solução para dar suporte aos argumentos nomeados by, lt e rev, de modo 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 esses parâmetros forem usados, você deve assumir que a lista já foi ordenada usando esses parâmetros. Consulte a documentação de sort para mais detalhes.
• Dê suporte a listas em que o elemento procurado se repete (encontre o primeiro e o último índice em que o elemento procurado é igual).

---

Fonte

Wikipedia