이분탐색 알고리즘

배열이 크기순으로 정렬되어 있을때 O(logN) 시간에 값의 위치를 탐색할 수 있는 알고리즘. 배열이 크기순으로 정렬되어 있기에 구역을 절반씩 나눠 원하는 값이 어떤 영역에 있는지 탐색을 반복해 위치를 특정한다.

logN의 시간복잡도가 얼마나 강력한지 설명하자면 N이 long타입의 최고 범위 10^18이라고 가정하더라도, O(log10^18) = O(18*log10) = 약 54. 무려 상수에 가깝게 줄어든다. 즉 억을 넘어 경단위의 문제도 풀이 가능하다.

이분탐색 알고리즘의 유형

이분탐색 알고리즘은 크게 2가지 목적으로 사용할 수 있다.
1. 정렬된 배열에서 특정 값 인덱스 탐색
2. 정렬된 배열에 값을 들어갈 인덱스 탐색

배열의 특정 값을 찾는 상황

def binarySearch(list, target):
    left = 0
    right = len(list) - 1
    
    while left <= right:
        mid = (right + left) // 2
        
        # 핵심 차이점
        if target == list[mid]:
            return mid
        
        elif target < list[mid]:
            right = mid - 1
        else :
            left = mid + 1
    
    return -1

result = [1, 1, 2, 2]

print(binarySearch(result, 0), binarySearch(result, 1), binarySearch(result, 2), binarySearch(result, 3))

# output: -1 1 2 -1 "-1은 탐색 실패를 의미한다"

배열의 값을 추가하려는 상황

Lower bound: 같은 값이 나오는 경우 처음 인덱스 반환

def binarySearch(list, target):
    left = 0
    right = len(list) - 1
    
    while left <= right:
        mid = (right + left) // 2
        # 핵심 차이점
        if target <= list[mid]:
            right = mid - 1
        else :
            left = mid + 1
    
    return left
    
result = [1, 1, 2, 2]

print(binarySearch(result, 0), binarySearch(result, 1), binarySearch(result, 2), binarySearch(result, 3))

# output: 0 0 2 4

Upper bound: 같은 값이 나오는 경우 마지막 인덱스 +1 반환 (Lower에서 등호하나만 빼서 구현했다.)

def binarySearch(list, target):
    left = 0
    right = len(list) - 1
    
    while left <= right:
        mid = (right + left) // 2
        # 핵심 차이점
        if target < list[mid]:
            right = mid - 1
        else :
            left = mid + 1
    
    return left
    
result = [1, 1, 2, 2]

print(binarySearch(result, 0), binarySearch(result, 1), binarySearch(result, 2), binarySearch(result, 3))

# output: 0 2 4 4

구현에 대한 팁

• 파라매트리 서치는 upper bound를 그대로 활용해서 풀이 가능하다.

• mid를 계산하는 과정에서 left와 right를 합하기에 overflow에 주의한다.
  해당 식으로 예방도 가능하다.

mid = left + (right - left) / 2

• 주로 구현이 제대로 되었는지 확인하는 방법은 조건문이 아래와 같은 경우에 정상적인 정답을 구하는가 확인하면 된다.

// 1을 찾는 문제인 경우
{0} // 정답이 없는 경우가 있다면 이것도 확인해줘야 한다.
{1} // 정답을 제대로 출력하는지 확인 + 경계값 첫번째 원소인 경우
{0, 1} // 경계값 마지막 원소인 경우
{0, 1, 1, 2} // upper, lower가 제대로 적용되었나 확인