7-1. 범위를 반 씩 줄여가는 탐색

이진 탐색 알고리즘

• 순차 탐색: 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법
• 이진 탐색: 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
                  (시작점, 끝점, 중간점을 이용하여 탐색 범위 설정)

이진 탐색 소스코드: 재귀적 구현

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start+end)//2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    # 중간점의 값보다 찾고자하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid+1, end)


# n(원소의 개수)과 target(찾고자하는 값) 입력받기
n, target = list(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) # 몇 번째 원소인지 출력하려고 +1을 함

 

이진 탐색 소스코드: 반복문 구현

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 = list(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)

 

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

from bisect import bisect_left, bisect_right

bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환

bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

 

파라메트릭 서치

최적화 문제를 결정문제(예/아니오)로 바꾸어 해결하는 기법으로 특정한 조건을 만족하는 값을 빠르게 찾는 문제가 그 예시이다.

-> 이진탐색으로 해결 가능