8.6. "bisect" --- Algoritmo de bisseção de vetor
************************************************

**Código Fonte:** Lib/bisect.py

======================================================================

Este módulo fornece suporte para manter uma lista em ordem de
classificação sem ter que classificar a lista após cada inserção. Para
longas listas de itens com operações de comparação custosas, isso pode
ser uma melhoria em relação à abordagem mais comum. O módulo é
denominado "bisect" porque usa um algoritmo de bisseção básico para
fazer seu trabalho. O código-fonte pode ser mais útil como um exemplo
funcional de algoritmo (as condições fronteiriças  já estão certas!).

As seguintes funções são fornecidas:

bisect.bisect_left(a, x, lo=0, hi=len(a))

   Localiza o ponto de inserção de *x* em *a* para manter a ordem de
   classificação. Os parâmetros *lo* e *hi* podem ser usados para
   especificar um subconjunto da lista que deve ser considerado; por
   padrão, toda a lista é usada. Se *x* já estiver presente em *a*, o
   ponto de inserção estará antes (à esquerda) de qualquer entrada
   existente. O valor de retorno é adequado para uso como o primeiro
   parâmetro para "list.insert()" supondo que *a* já esteja ordenado.

   O ponto de inserção retornado *i* particiona o vetor *a* em duas
   metades de modo que "all(val < x for val in a[lo:i])" para o lado
   esquerdo e "all(val >= x for val in a[i:hi])" para o lado direito.

bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))

   Semelhante a "bisect_left()", mas retorna um ponto de inserção que
   vem depois (à direita de) qualquer entrada existente de *x* em *a*.

   O ponto de inserção retornado *i* particiona o vetor *a* em duas
   metades de modo que "all(val <= x for val in a[lo:i])" para o lado
   esquerdo e "all(val > x for val in a[i:hi])" para o lado direito.

bisect.insort_left(a, x, lo=0, hi=len(a))

   Insere *x* em *a* na ordem de classificação. Isso é equivalente a
   "a.insert(bisect.bisect_left(a, x, lo, hi), x)" supondo que *a* já
   esteja ordenado. Lembre-se de que a pesquisa O(log n) é dominada
   pela lenta etapa de inserção O(n).

bisect.insort_right(a, x, lo=0, hi=len(a))
bisect.insort(a, x, lo=0, hi=len(a))

   Semelhante a "insort_left()", mas inserindo *x* em *a* após
   qualquer entrada existente de *x*.

Ver também:

  Receita de SortedCollection que usa bisect para construir uma classe
  de coleção completa com métodos de pesquisa diretos e suporte para
  uma função chave. As chaves são pré-calculadas para economizar em
  chamadas desnecessárias para a função chave durante as pesquisas.


8.6.1. Pesquisando em listas ordenadas
======================================

As funções "bisect()" acima são úteis para encontrar pontos de
inserção, mas podem ser complicadas ou difíceis de usar para tarefas
comuns de pesquisa. As cinco funções a seguir mostram como
transformá-las nas pesquisas padrão para listas ordenadas:

   def index(a, x):
       'Locate the leftmost value exactly equal to x'
       i = bisect_left(a, x)
       if i != len(a) and a[i] == x:
           return i
       raise ValueError

   def find_lt(a, x):
       'Find rightmost value less than x'
       i = bisect_left(a, x)
       if i:
           return a[i-1]
       raise ValueError

   def find_le(a, x):
       'Find rightmost value less than or equal to x'
       i = bisect_right(a, x)
       if i:
           return a[i-1]
       raise ValueError

   def find_gt(a, x):
       'Find leftmost value greater than x'
       i = bisect_right(a, x)
       if i != len(a):
           return a[i]
       raise ValueError

   def find_ge(a, x):
       'Find leftmost item greater than or equal to x'
       i = bisect_left(a, x)
       if i != len(a):
           return a[i]
       raise ValueError


8.6.2. Outros Exemplos
======================

A função "bisect()" pode ser útil para pesquisas em tabelas numéricas.
Este exemplo usa "bisect()" para pesquisar uma nota em letra para uma
pontuação de exame (digamos) com base em um conjunto de pontos de
interrupção numéricos ordenados: 90 e acima é um "A", 80 a 89 é um "B"
e por aí vai:

   >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
   ...     i = bisect(breakpoints, score)
   ...     return grades[i]
   ...
   >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
   ['F', 'A', 'C', 'C', 'B', 'A', 'A']

Ao contrário da função "sorted()", não faz sentido que as funções
"bisect()" tenham argumentos *key* ou *reversed* porque isso levaria a
um design ineficiente (chamadas sucessivas para funções bisect não
"lembrariam" de todas as pesquisas de chave anteriores).

Em vez disso, é melhor pesquisar uma lista de chaves pré-computadas
para encontrar o índice do registro em questão:

   >>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
   >>> data.sort(key=lambda r: r[1])
   >>> keys = [r[1] for r in data]         # precomputed list of keys
   >>> data[bisect_left(keys, 0)]
   ('black', 0)
   >>> data[bisect_left(keys, 1)]
   ('blue', 1)
   >>> data[bisect_left(keys, 5)]
   ('red', 5)
   >>> data[bisect_left(keys, 8)]
   ('yellow', 8)
