[알고리즘] 이코테(4) - 이진 탐색 / 이분 탐색

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/94RC-DsGMLo?si=iDSiDtzOFIj_b1Ym

---

이진 탐색 binary search

출처: mathwarehouse

요약

순차 탐색: 리스트 내 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인

이진 탐색: 정렬된 리스트 내에서, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색

 

순서

• 리스트를 정렬한다.
• while start <= end인 동안 다음을 반복한다.
• start와 end의 중간점을 mid로 설정한다.
• mid와 구하고자 하는 값인 target을 비교한다.
• mid < target이면, 검색 범위를 높여야 한다. start = mid + 1로 설정해서 재귀적으로 이진 탐색한다.
• mid > target이면, 검색 범위를 낮춰야 한다. end = mid - 1로 설정해서 재귀적으로 이진 탐색한다.
• mid == target인 경우 mid 값을 반환한다.

파라메트릭 서치

파라메트릭 서치란 최적화 문제(특정한 조건을 만족하는 가장 알맞은 값을 찾는)를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 기법.

일반적으로 코테에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능.

 

구현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: # array[mid] < target:
        return binary_search(array, target, mid + 1, end)

구현2: 반복문

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: # array[mid] < target:
            start = mid + 1
    
    return None

 

구현3: 라이브러리

from bisect import bisect_left, bisect_right

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

print(bisect_left(a, x)) # 2
print(bisect_right(a, x)) # 4

 

시간 복잡도

매 단계에서 탐색 범위를 절반으로 줄여나가므로 탐색 횟수는 로그 스케일로 증가한다.

따라서 평균, 최악의 상황에서 O(logN)의 시간복잡도를 갖는다.

 

공간 복잡도

반복문 구현: O(1). 추가적인 저장 공간이 필요하지 않다.

재귀적 구현: O(logN). 재귀 호출로 인한 스택이 필요하다.

 

예제 1: 떡볶이 떡 만들기

n, m = map(int, input().split())
heights = list(map(int, input().split()))
result = 0

start = 0
end = max(heights)

while start <= end:
    
    total = 0
    mid = (start + end) // 2

    for hei in heights: # 기준치 보다 자르려는 떡의 긴 경우에만, 차이만큼 total에 더한다.
        if hei > mid:
            total += hei - mid

    if total < m: # 조건을 만족하지 못 하면, 기준치를 줄여, 남는 떡의 길이를 늘린다.
        end = mid - 1
    else: # 조건을 만족한 경우 result를 갱신한다. 기준치를 줄이고, 남는 떡의 길이를 늘려 최적값을 찾는다.
        result = mid
        start = mid + 1

print(result)

 

예제 2-1: 특정 수 개수: 일반

def count_by_value(array, x): # 정렬된 수열에서 값이 x인 원소의 개수를 세는 메서드
    n = len(array) # 데이터의 개수
    
    first_idx = first(array, x, 0, n-1) # x가 처음 등장한 인덱스
    if first_idx == None: # 수열에 x가 존재하지 않는 경우
        return 0 # 값이 X인 원소의 개수는 0개이므로 0 반환
    
    last_idx = last(array, x, 0, n-1) # x가 마지막으로 등장한 인덱스
    return last_idx - first_idx + 1


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

    # target == mid인 동시에, mid - 1은 target보다 작은 경우
    # 조건을 만족하는 가장 왼쪽에 있는 인덱스인 경우
    if target == array[mid] and (mid == 0 or target > array[mid - 1]):
        return mid
    
    elif target <= array[mid]:
        return first(array, target, start, mid - 1)
    
    else:
        return first(array, target, mid + 1, end)


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

    if array[mid] == target and (mid == 0 or array[mid + 1] > target):
        return mid
    
    elif array[mid] > target:
        return last(array, target, start, mid - 1)
    
    else:
        return last(array, target, mid + 1, end)


n, x = map(int, input().split())
array = list(map(int, input().split()))

count = count_by_value(array, x)
print(count if count > 0 else -1)

 

예제 2-2: 특정 수 개수: 라이브러리

from bisect import bisect_left, bisect_right

def get_count_by_bisect(array, x):
    left = bisect_left(array, x)
    right = bisect_right(array, x)
    return right - left

n, x = map(int, input().split())
array = list(map(int, input().split()))

count = get_count_by_bisect(array, x)

if count == 0:
    print(-1)
else:
    print(count)