"bisect" --- 배열 이진 분할 알고리즘
************************************

**소스 코드:** Lib/bisect.py

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

이 모듈은 정렬된 리스트를 삽입 후에 다시 정렬할 필요 없도록 관리할 수
있도록 지원합니다. 값비싼 비교 연산이 포함된 항목의 긴 리스트의 경우,
이는 선형 검색이나 빈번한 재정렬에 비해 개선된 것입니다.

The module is called "bisect" because it uses a basic bisection
algorithm to do its work.  Unlike other bisection tools that search
for a specific value, the functions in this module are designed to
locate an insertion point. Accordingly, the functions never call an
"__eq__()" method to determine whether a value has been found.
Instead, the functions only call the "__lt__()" method and will return
an insertion point between values in an array.

참고:

  The functions in this module are not thread-safe. If multiple
  threads concurrently use "bisect" functions on the same sequence,
  this may result in undefined behaviour. Likewise, if the provided
  sequence is mutated by a different thread while a "bisect" function
  is operating on it, the result is undefined. For example, using
  "insort_left()" on the same list from multiple threads may result in
  the list becoming unsorted.

다음과 같은 함수가 제공됩니다:

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

   정렬된 순서를 유지하도록 *a*에 *x*를 삽입할 위치를 찾습니다. 매개
   변수 *lo* 와 *hi*는 고려해야 할 리스트의 부분집합을 지정하는 데 사
   용될 수 있습니다; 기본적으로 전체 리스트가 사용됩니다. *x*가 *a*에
   이미 있으면, 삽입 위치는 기존 항목 앞(왼쪽)이 됩니다. 반환 값은 *a*
   가 이미 정렬되었다고 가정할 때 "list.insert()"의 첫 번째 매개 변수
   로 사용하기에 적합합니다.

   반환된 삽입 위치 *ip*는 배열 *a*를 두 개의 조각으로 분할하여, 왼쪽
   에 대해서는 "all(elem < x for elem in a[lo : ip])"이 참이고, 오른쪽
   에 대해서는 "all(elem >= x for elem in a[ip : hi])"이 참이 되도록
   만듭니다.

   *key* specifies a *key function* of one argument that is used to
   extract a comparison key from each element in the array.  To
   support searching complex records, the key function is not applied
   to the *x* value.

   If *key* is "None", the elements are compared directly and no key
   function is called.

   버전 3.10에서 변경: *key* 매개 변수를 추가했습니다.

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

   "bisect_left()"와 비슷하지만, *a*에 있는 *x*의 기존 항목 뒤(오른쪽)
   에 오는 삽입 위치를 반환합니다.

   반환된 삽입 위치 *ip*는 배열 *a*를 두 개의 조각으로 분할하여, 왼쪽
   에 대해서는 "all(elem <= x for elem in a[lo : ip])"이 참이고, 오른
   쪽에 대해서는 "all(elem > x for elem in a[ip : hi])"이 참이 되도록
   만듭니다.

   버전 3.10에서 변경: *key* 매개 변수를 추가했습니다.

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

   Insert *x* in *a* in sorted order.

   This function first runs "bisect_left()" to locate an insertion
   point. Next, it runs the "insert()" method on *a* to insert *x* at
   the appropriate position to maintain sort order.

   To support inserting records in a table, the *key* function (if
   any) is applied to *x* for the search step but not for the
   insertion step.

   Keep in mind that the *O*(log *n*) search is dominated by the slow
   *O*(*n*) insertion step.

   버전 3.10에서 변경: *key* 매개 변수를 추가했습니다.

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

   "insort_left()"와 비슷하지만, *a*에 *x*를 *x*의 기존 항목 다음에 삽
   입합니다.

   This function first runs "bisect_right()" to locate an insertion
   point. Next, it runs the "insert()" method on *a* to insert *x* at
   the appropriate position to maintain sort order.

   To support inserting records in a table, the *key* function (if
   any) is applied to *x* for the search step but not for the
   insertion step.

   Keep in mind that the *O*(log *n*) search is dominated by the slow
   *O*(*n*) insertion step.

   버전 3.10에서 변경: *key* 매개 변수를 추가했습니다.


Performance Notes
=================

When writing time sensitive code using *bisect()* and *insort()*, keep
these thoughts in mind:

* Bisection is effective for searching ranges of values. For locating
  specific values, dictionaries are more performant.

* The *insort()* functions are *O*(*n*) because the logarithmic search
  step is dominated by the linear time insertion step.

* The search functions are stateless and discard key function results
  after they are used.  Consequently, if the search functions are used
  in a loop, the key function may be called again and again on the
  same array elements. If the key function isn't fast, consider
  wrapping it with "@functools.cache" to avoid duplicate computations.
  Alternatively, consider searching an array of precomputed keys to
  locate the insertion point (as shown in the examples section below).

더 보기:

  * Sorted Collections is a high performance module that uses *bisect*
    to managed sorted collections of data.

  * bisect를 사용하여 직접적인 검색 메서드와 키 함수 지원을 포함하는
    완전한 기능을 갖춘 컬렉션 클래스를 만드는 SortedCollection recipe.
    검색 중에 불필요한 키 함수 호출을 피하고자 키는 미리 계산됩니다.


정렬된 리스트 검색하기
======================

위의 bisect functions는 삽입 위치를 찾는 데 유용하지만, 일반적인 검색
작업에 사용하기가 까다롭거나 어색할 수 있습니다. 다음 다섯 함수는 정렬
된 리스트에 대한 표준 조회로 변환하는 방법을 보여줍니다:

   def index(a, x):
       'x 와 정확히 같은 가장 왼쪽의 값을 찾습니다'
       i = bisect_left(a, x)
       if i != len(a) and a[i] == x:
           return i
       raise ValueError

   def find_lt(a, x):
       'x보다 작은 가장 오른쪽 값을 찾습니다'
       i = bisect_left(a, x)
       if i:
           return a[i-1]
       raise ValueError

   def find_le(a, x):
       'x보다 작거나 같은 가장 오른쪽 값을 찾습니다'
       i = bisect_right(a, x)
       if i:
           return a[i-1]
       raise ValueError

   def find_gt(a, x):
       'x보다 큰 가장 왼쪽 값을 찾습니다'
       i = bisect_right(a, x)
       if i != len(a):
           return a[i]
       raise ValueError

   def find_ge(a, x):
       'x보다 크거나 같은 가장 왼쪽 항목을 찾습니다'
       i = bisect_left(a, x)
       if i != len(a):
           return a[i]
       raise ValueError


예제
====

"bisect()" 함수는 숫자 테이블 조회에 유용할 수 있습니다. 이 예제는
"bisect()"를 사용하여 (가령) 시험 점수에 대한 문자 등급을 조회하는데,
정렬된 숫자 경계점 집합에 기반합니다: 90 이상은 'A', 80에서 89는 'B'
등입니다:

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

The "bisect()" and "insort()" functions also work with lists of
tuples.  The *key* argument can serve to extract the field used for
ordering records in a table:

   >>> from collections import namedtuple
   >>> from operator import attrgetter
   >>> from bisect import bisect, insort
   >>> from pprint import pprint

   >>> Movie = namedtuple('Movie', ('name', 'released', 'director'))

   >>> movies = [
   ...     Movie('Jaws', 1975, 'Spielberg'),
   ...     Movie('Titanic', 1997, 'Cameron'),
   ...     Movie('The Birds', 1963, 'Hitchcock'),
   ...     Movie('Aliens', 1986, 'Cameron')
   ... ]

   >>> # 1960년 이후 개봉한 최초의 영화를 찾습니다
   >>> by_year = attrgetter('released')
   >>> movies.sort(key=by_year)
   >>> movies[bisect(movies, 1960, key=by_year)]
   Movie(name='The Birds', released=1963, director='Hitchcock')

   >>> # 정렬 순서를 유지하면서 영화를 삽입합니다
   >>> romance = Movie('Love Story', 1970, 'Hiller')
   >>> insort(movies, romance, key=by_year)
   >>> pprint(movies)
   [Movie(name='The Birds', released=1963, director='Hitchcock'),
    Movie(name='Love Story', released=1970, director='Hiller'),
    Movie(name='Jaws', released=1975, director='Spielberg'),
    Movie(name='Aliens', released=1986, director='Cameron'),
    Movie(name='Titanic', released=1997, director='Cameron')]

키 함수가 비싸면, 미리 계산된 키 목록을 검색하여 레코드의 인덱스를 찾
으면 반복돠는 함수 호출을 피할 수 있습니다:

   >>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
   >>> data.sort(key=lambda r: r[1])       # 또는 operator.itemgetter(1) 를 사용하세요.
   >>> keys = [r[1] for r in data]         # 미리 계산된 키 리스트.
   >>> 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)
