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

In [1]:

from IPython.core.display import display, HTML

display(HTML("<style>.container { width:100% !important; }</style>"))

View Source

Binary Search Algorithm¶

Objective¶

1. 이진 탐색 알고리즘 특징
2. 이진 탐색 알고리즘 구현방법
3. 이진 탐색을 활용한 Parametric Search

1. 이진 탐색 알고리즘의 특징¶

• 정렬된 상태의 데이터에서 빠르게 탐색을 하기 위한 알고리즘
• 탐색 범위를 반으로 줄여가면서 실시하며 이는 연산 횟수가 $log{_2}{N}$ 의미한다. 따라서 시간복잡도는 O($log{N}$) 이다.
• 이와는 반대로 순차적으로 데이터를 하나하나 확인하는 방법은 순차 탐색(Sequential Search) 이며 시간복잡도는 O(N) 이다.
• 관련된 자료구조로는 이진 탐색 트리(Binary Search Tree) 가 있다. 아래 링크 참고
  • 이진 탐색 트리(Binary Search Tree)설명1
  • 이진 탐색 트리(Binary Search Tree)설명2
• 이진 탐색 트리의 탐색 과정은 이진 탐색과 조금은 다르지만 그 기저의 원리(반띵)는 같다.
• 시간복잡도에서 볼수 있듯이 빠른 탐색이 가능하여 데이터베이스 시스템이나 파일시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위해 해당 자료구조를 사용한다.

2. 이진 탐색 알고리즘 구현 방법¶

• 이진 탐색은 재귀 또는 반복문으로 구현할 수 있다.
• 개인적으로 반복문이 선호한다.
  • 시간복잡도는 같으나 재귀적으로 함수를 호출시 비용이 발생하기 때문이며,
  • 뒤에 나올 Parametric Search에 적용하기 훨씬 쉽기 때문이다.

# 재귀 활용
def binary_search_recur(array, target, start, end):
    if start > end:
        return None

    mid = (start+end) // 2
    if array[mid] == target:
        return mid
    elif if array[mid] > target:
        return binary_search(array, target, start, mid-1)
    else:
        return binary_search(array, target, mid+1, end)


# 반복문 활용
def binary_search_loop(array, target, start, end):
    while start <= end:
        mid = (start+end) // 2

        if array[mid] == target:
            return mid
        elif if array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

array = [1,3,5,7,9,11,13,15,17,19]
end = len(array) - 1
start = 0
target = 7

binary_search_recur(array, target, start, end)
binary_search_loop(array, target, start, end)

3. 이진 탐색을 활용한 Parametric Search¶

• Parametric Search 란

  • 최적화 문제를 결정문제('예' 혹은 '아니오'답하는 문제)로 바꾸어 해결하는 기법
  • 원하는 조건을 만족하는 가장 알맞은 값을 찬는 문제
  • 이진 탐색을 활용하며 범위를 좁혀간다.
  • 이진 탐색의 알고리즘 문제(코딩 테스트 한정)는 거의 Parametric Search 문제이며, 해당 방법으로 거의다 풀리는 것 같다.

• 아래와 같은 Template를 사용

# Binary Search - Parametric Search Template

# Parametric Search 함수 : True 혹은 False 답하는 문제
# args 같은 경우 문제에 따라 변동
def is_possible(mid, args):
    # 가능하면 True 불가능하면 False 반환 
    if condition is True:
        return True
    return False

# Binray search
# lower 값이 upper 보다 크면 exit 
while lower <= upper:
    mid = (lower + upper) // 2

    # 문제에 따라 변동이 있지만 
    # 특정 조건이 True면 upper = mid -1,
    # 특정 조건이 False면 lower = mid + 1
    if is_possible(mid, args):
        upper = mid - 1
    else:
        lower = mid + 1

# 결과값 - 문제에 따라 upper + 1 이 될 수도 있음에 주의         
print(lower - 1)

3-1. 실전 문제 예시 1¶

• https://www.acmicpc.net/problem/2110

n, m = map(int, input().split(' '))
house = []
for _ in range(n):
    house.append(int(input()))

house.sort()
lower = 1
upper = house[-1]

def is_possible(mid, house, m):
    cnt = 1
    cur_house = house[0]
    for i in range(1, len(house)):
        if house[i] - cur_house >= mid:
            cnt += 1
            cur_house = house[i]
    if cnt >= m:
        return True
    return False

while lower <= upper:
    mid = (lower + upper) // 2
    if not is_possible(mid, house, m):
        upper = mid - 1
    else:
        lower = mid + 1

print(lower-1)

3-1. 실전 문제 예시 2¶

• https://programmers.co.kr/learn/courses/30/lessons/43236

def is_possible(rocks, n, mid):
    remove_rock = 0
    cur_rock = 0
    for i in rocks:
        if i - cur_rock < mid:
            remove_rock += 1
        if i >= mid + cur_rock:
            cur_rock = i
    return remove_rock <= n

def solution(distance, rocks, n):
    rocks.sort()
    lower = 1
    upper = distance

    while lower<=upper:
        mid = (lower + upper) // 2
        if is_possible(rocks, n, mid):
            lower = mid + 1
        else:
            upper = mid - 1

    return lower - 1