2분 찾기: Python 구현(순환 & 귀속)

위키백과: 컴퓨터 과학에서 2분 검색(영어:binary search), 절반 검색(영어:half-interval search), 대수 검색(영어:logarithmic search)은 질서수 그룹에서 특정한 요소를 찾는 검색 알고리즘이다.검색 과정은 수조의 중간 요소에서 시작하고 중간 요소가 마침 찾으려는 요소라면 검색 과정이 끝난다.만약 특정한 원소가 중간 원소보다 크거나 작다면, 수조가 중간 원소보다 크거나 작으면 그 절반에서 찾고, 시작과 같이 중간 원소부터 비교한다.만약 어떤 단계에서 수조가 비어 있다면, 찾을 수 없다는 것을 나타낸다.이런 검색 알고리즘은 매번 비교할 때마다 검색 범위를 절반으로 줄인다.
2분 검색 알고리즘 분류 검색 알고리즘 데이터 구조 그룹 최악 시간 복잡도 {\displaystyle O(\logn)} 최적 시간 복잡도 {\displaystyle O(1)} 평균 시간 복잡도 {\displaystyle O(\logn)} 최악 공간 복잡도 교체: {\displaystyle O(1)} 귀속: {\displaystyle O(\logn)} 2분 검색 상황에서의 복잡도는 대수 시간입니다.{\displaystyle O(\logn)}차 비교 작업을 진행합니다({\displaystyle n}은 여기에서 수조의 원소 수량이고, {\displaystyle O}는 대O기호이며, {\displaystyle\log}는 대수입니다.2분 검색은 상수 공간을 사용하는데 어떤 크기의 입력 데이터에 대해서도 알고리즘이 사용하는 공간은 똑같다.입력 데이터의 수량이 매우 적지 않으면, 2분 검색은 선형 검색보다 빠르지만, 수조는 반드시 사전에 정렬되어야 한다.2분 검색은 질서수 그룹에만 유효합니다
& & 잔소리 그만하고 코드 올리기 &

1, 순환 실현

#  （while）
def binary_search(li,n):
    left = 0
    right = len(li) - 1
    while left <= right:
        mid = (right + left) // 2
        if li[mid] < n:
            left = mid +1
        elif li[mid] > n:
            right = mid - 1
        else:
            return mid
    return 0
li = []
while 1:
    a = input(' ， ，# ：')
    if a=='#':
        break
    a = int(a)
    li.append(a)
li.sort()# 
print(li)
while 1:
    x = input(' ：')
    if x:
        x = int(x)
        result = binary_search(li, x)
        if result == 0:
            print(' ， ！')
        else:
            print(f' {result}')
    else:
        print(' ！')

2, 반복 실현

#  
def binary_search(li,n,left,right):
    if left <= right:# 
        mid = (right + left) // 2
        if li[mid] < n:
            return binary_search(li,n,mid+1,right)
        elif li[mid] > n:
            return binary_search(li,n,left,mid-1)
        else:
            return mid
    else:
        return -1

li = []
while 1:
    a = input(' ,# ：')
    if a=='#':
        break
    a = int(a)
    li.append(a)
print(f' {li}')
li.sort()# 
print(f' {li}')
while 1:
    x = input(' ：')
    if x:
        x = int(x)
        left = 0
        right = len(li) - 1
        result = binary_search(li, x, left, right)
        if result == -1:
            print(' ， ！')
        else:
            print(f' {result}!')
    else:
        print(' ！')

주의해야 할 것은 2분 찾기는 시간 복잡도가 낮지만 내장 함수 index는 선형 찾기를 사용합니다. 2분 찾기의 조건은 반드시 질서정연해야 하기 때문입니다.