[이코테_코딩테스트] 이진 탐색 알고리즘 (Binary Search)

date

Jul 30, 2023

slug

coding-test-binary-search

author

status

Public

이진 탐색 알고리즘 (Binary Search)

순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정

이진 탐색 동작 예시

이지 정렬된 10개의 데이터 중 값이 ‘4’인 원소를 찾는 예시

[Step 1] 시작점 : 0, 끝점 : 9, 중간점 : 4 (소수점 이하 제거) ← Index 값

이미 정렬이 되어있음, 중간점과 비교 8 > 4

중간점 포함 이후(오른쪽)는 확인할 필요가 없음 → 8보다 큰 수들

중간점 위치를 왼쪽으로 옮김

[Step 2] 시작점 : 0, 끝점 : 3, 중간점 : 1

중간점과 비교 2 < 4

중간점 포함 왼쪽은 확인할 필요 없음

시작점 위치를 중간점 오른쪽으로 옮김

[Step 3] 시작점 : 2, 끝점 : 3, 중간점 : 2

중간점 비교 4 = 4

탐색 종료

이진 탐색의 시간 복잡도

단계마다 탐색 범위를 2로 나누는 것과 동일 → 연산 횟수는 에 비례

예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개 가량의 데이터만 남는다.

2단계를 거치면 8개
3단계를 거치면 4개

따라서 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 을 보장한다.

이진 탐색 소스코드 - 재귀적 구현 (Python)


def binary_search(arrary, target, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2

    if arrary[mid] == target:
        return mid
    elif arrary[mid] > target:
        return binary_search(arrary, target, start, mid - 1)
    else:
        return binary_search(arrary, 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("해당 원소 {}은 {}번째에 있으며, 인덱스 값은 {}입니다.".format(target, result + 1, result))

이진 탐색 소스코드 - 반복문 구현 (Python)


def binary_search(arrary, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if arrary[mid] == target:
            return mid
        elif arrary[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("해당 원소 {}은 {}번째에 있으며, 인덱스 값은 {}입니다.".format(target, result + 1, result))

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

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

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


from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x))
print(bisect_right(a, x))

값이 특정 범위에 속하는 데이터 개수 구하기


from bisect import bisect_right, bisect_left

# 값이 [left_value, right_value]인 데이터의 개수 반환 함수
def range_count(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)

    return right_index - left_index

a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 데이터 개수 출력
print(range_count(a, 4, 4))

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(range_count(a, -1, 3))

파라메트릭 서치 (Parametric Search)

최적화 문제를 결정 문제(”예” 혹은 “아니오”)로 바꾸어 해결하는 기법

ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

일반적으로 코딩테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 5. 이진 탐색” 영상을 보고 작성하였습니다.