[알고리즘] 범위를 반씩 좁혀가는 이진 탐색 - 파이썬(Python)

순차 탐색

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 리스트의 첫 번째 원소부터 찾고자 하는 데이터와 일치하는지 확인하여 일치하면 탐색 종료, 일치하지 않으면 다음 원소로 이동한다.

# 순차 탐색
def sequential_search(n, target, array):
    for i in range(n):
        if array[i] == target:
            return i+1  # 현재 위치 반환 (-번째)


 array = ['S', 'T', 'A', 'R']  # 임의 지정 리스트
 print("리스트 속 A의 위치는 " + sequential_search(len(array), 'A', array) + "입니다.") # 탐색 결과 출력

 

이진 탐색

• 리스트 내의 데이터가 정렬되어 있어야만 사용 가능
• 범위를 계속 줄여나가며 찾으려는 데이터와 범위의 중간점에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾아가는 방법

예시) 정렬된 10개의 데이터 중에서 값이 4인 원소 찾기

1. 시작점과 끝점 사이의 중간점을 구한다. 중간점이 실수일 때는 소수점 이하를 버린다. 그림에서 시작점은 [0], 끝점은 [9]이므로 중간점은 [4]이다. 따라서, 중간점 [4]의 데이터 8과 찾으려는 데이터 4를 비교한다. 중간점의 데이터 8이 더 크므로 끝점을 [4]의 이전인 [3]으로 옮겨 범위를 좁힌다.

   

2. 시작점 [0], 끝점 [3]의 중간점 [1]에 위치한 데이터 2는 찾으려는 데이터 4보다 작으므로 시작점을 [2]로 옮겨 범위를 다시한번 좁힌다.

   

3. 시작점 [2], 끝점 [3]의 중간점 [2]에 위치한 데이터 4는 찾으려는 데이터 4와 같으므로 탐색을 종료한다.

   

# 반복문으로 구현한 이진 탐색

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2  # 중간점 인덱스
        if array[mid] == target:
            return mid  # 탐색 완료 (중간점 인덱스 반환)
        elif array[mid] > target:
            end = mid - 1  # 중간점의 값보다 찾고자 하는 값이 작은 경우 끝점 조정
        else:
            start = mid + 1  # 중간점의 값보다 찾고자 하는 값이 큰 경우 시작점 조정
    return None  # 찾고자 하는 값이 없는 경우

# 원소의 개수(n)과 찾고자하는 값(target) 입력받기
n, target = map(int, input().split())
# 전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 결과 출력
result = binary_search(array, target, 0, n-1)
if result == None:
    print("해당 데이터는 존재하지 않습니다.")
else: 
    print(result + 1)

 

파이썬 이진탐색 라이브러리 Bisect

※ 반드시 data가 사전에 정렬되어 있어야 함

• bisect.bisect\_left(data, x): data내에 x가 들어갈 수 있는 가장 왼쪽의(작은) 인덱스 반환
• bisect.bisect\_right(data, x): data내에 x가 들어갈 수 있는 가장 오른쪽은(큰) 인덱스 반환

import bisect

data = [1, 2, 2, 3, 4]
x = 2

print(bisect.bisect_left(data, x))  # 1
print(bisect.bisect_right(data, x))  # 3