이등분 배열을 위한 이진 알고리즘

이 모듈은 요소 삽입 후 정렬을 유지하기 위해 정렬된 대기열 목록을 구현합니다. 많은 양의 데이터가 포함된 목록의 경우 요소를 삽입하고 정렬된 상태로 유지하는 것은 계산 비용이 매우 많이 듭니다. 이 모듈은 주로 이진 알고리즘을 기반으로 구현되는 bisect 알고리즘을 구현합니다.

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

순서가 지정된 목록 a에 요소 x를 삽입하고 순서를 변경하지 않고 유지한 후 삽입된 위치를 반환합니다. 매개변수 lo와 hi는 판정 목록의 범위를 나타내며, 기본값은 전체 범위이다. 삽입된 요소 x가 목록 a에 이미 존재하는 경우 기존 요소의 왼쪽에 삽입됩니다.

예:

#Python 3.4

가져오기 이등분

l = [8, 5, 6, 6, 3]

l.sort()

인쇄(l)

print(bisect.bisect_left(l, 0))

인쇄(l)

print(bisect.bisect_left(l, 5))

print(bisect.bisect_left(l, 7))

결과 출력은 다음과 같습니다.

[3, 5, 6, 6, 8]

0

[3, 5, 6, 6, 8]

1

4

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

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

순서 있는 대기열 a에서 x가 삽입될 수 있는 위치를 찾아 대기열을 순서대로 유지합니다. 삽입된 값이 큐에 있는 값과 동일하면 동일한 요소의 오른쪽에 삽입되고 이 위치의 인덱스 값이 반환됩니다.

예:

#python 3.4

가져오기 이등분

l = [8, 5, 6, 6, 3]

l.sort()

인쇄(l)

print(bisect.bisect_right(l, 0))

인쇄(l)

print(bisect.bisect(l, 5))

print(bisect.bisect(l, 7))

결과 출력은 다음과 같습니다.

[3, 5, 6, 6, 8]

0

[3, 5, 6, 6, 8]

2

4

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

x 요소를 대기열 a에 삽입하고 대기열을 정렬합니다. a.insert(bisect.bisect_left(a, x, lo, hi), x)와 동일해야 합니다.

예:

#python 3.4

가져오기 이등분

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

bisect.insort_left(l, 0)

print(l)

bisect.insort_left(l, 5)

print(l)

bisect.insort_left(l, 7)

print(l)

결과 출력은 다음과 같습니다:

[3, 5, 6, 6, 8]

[0, 3, 5, 6, 6, 8]

[0 , 3, 5, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 7, 8]

이등분합니다. insort_right(a , x, lo=0, hi=len(a))

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

요소 삽입 x into a 큐에서 동일한 요소가 발견되면 동일한 요소의 오른쪽에 삽입됩니다.

예:

#python 3.4

가져오기 이등분

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

bisect.insort_right(l, 0)

print(l)

bisect.insort(l, 5)

print(l)

bisect.insort(l, 7)

print(l)

결과 출력은 다음과 같습니다:

[3, 5, 6, 6, 8]

[0, 3, 5, 6, 6, 8]

[0 , 3, 5, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 7, 8]

사용 위 함수 간단한 캡슐화:

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]

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):

'가장 왼쪽 항목 찾기 to x'

i = bisect_left(a, x)

if i != len(a):

return a[i]

인상 ValueError

학생 성적을 ABCDF 성적로 변환하는 데 사용:

#python 3.4

import bisect

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):

i = bisect.bisect(breakpoints, Score)

성적 반환 [ i]

print([33, 99, 77, 70, 89, 90, 100])

print([33, 99, 77, 70의 점수에 대한 등급(점수) , 89, 90, 100]])

결과 출력은 다음과 같습니다.

[33, 99, 77, 70, 89, 90, 100]

[ 'F', 'A', 'C', 'C', 'B', 'A', 'A']