Algorithm 5. 이진탐색(binary search)

오늘은 순서대로가 아니라 코테에서 자주 등장하는 이진(이분)탐색에 대해서 작성해볼 것이다. 

이진탐색은 교재 p.186 Chapter 7에서 등장한다.

 

순차탐색

- 리스트 안에 있는 특정 target을 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인

- 보통 정렬되어 있지 않은 데이터에서 target을 찾을 때 사용.

- 앞에서부터 데이터를 확인하기 때문에 데이터가 N개일 때 최악의 경우 시간복잡도는 O(N)

이진탐색

-  배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘.

- 정렬이 되어있다면 매우 빠르게 데이터를 찾을 수 있는 알고리즘. 

- 데이터를 찾기위해 (시작점, 끝점, 중간점)을 이용하여 탐색.

- 한번 확인할 때 마다 확인하는 원소의 개수가 절반씩 줄어들기 때문에 시간복잡도가 O(logN)

 

원리는 시작점과 끝점을 지정한 뒤 중앙점이 우리가 찾으려는 타겟보다 클 경우, 구간을 [시작점, (중간점-1)]로 줄여서 다시 반복하고, 중앙점이 타겟보다 작을 경우 구간을 [(중간점+1), 끝점]으로 정하여 다시 반복. 

위의 예시를 통해서 설명해보겠다. (그림과 같이 보세여)

1. list의 맨처음 인덱스와 마지막 인덱스를 start, end로 지정( start=0 / end=16)

2. 이진탐색 시작 ->현재 구간의 중심 인덱스를 찾음  mid=(start+end)//2=8  (start=0 / end=16 / mid=8)

3. list[mid]와 target을 비교해줌. list[mid]=list[8]=23 < tartget=37 

mid값이 target보다 작기 때문에 start=mid+1로 바꿔주고, end는 그대로 하고 이진탐색 재수행 ( start=9 / end= 16 / mid=12)

4. list[mid]=list[12]=41 > target이기 때문에 start는 그대로, end는 mid-1로 바꿔주고 이진탐색 재수행 (start=9 / end=11/ mid=10)

5. list[mid]=list[10]=31<target이기 때문에 start=mid+1, end는 그대로 이진탐색 재수행 (start=11 / end=11 / mid=11)

6. list[mid]=list[11]=37=target이므로 종료하고 mid 반환.

이진탐색(재귀)

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

    if array[mid] == target:
        return 1
    # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
    else:
        return binary_search(array, target, mid + 1, end)

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

result = binary_search(array, target, 0, n - 1)

이진탐색(반복문)

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

        # 원하는 값 찾은 경우 인덱스 반환
        if array[mid] == target:
            return 1
        # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
        elif array[mid] > target:
            end = mid - 1
        # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
        else:
            start = mid + 1

    return None


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

result = binary_search(array, target, 0, n - 1)

말로 설명하는 것보다 코드를 보는 것이 이해가 잘 될 수도있다. 이진탐색의 코드는 위와 같이 재귀형식으로도 짤 수 있고, 반복문 형식으로도 짤 수 있는데 재귀로 짤 경우 가독성이 좋고 이해하기 쉬워보이지만, 메모리를 더 잡아먹는다고 한다. 따라서 일반적으로 반복문을 이용하여 구현하면 좋을 것 같다.

bisect 라이브러리 (bisect_left, bisect_right)

파이썬의 경우에는 bisect라는 이진탐색을 구현해주는 라이브러리가있다. 

• 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))
>>> 2

print(bisect_right(a, x))
>>> 4

[Upper bound & Lower bound]

위와 같이 이진탐색은 특정값을 찾을 때도 많이 사용되지만, 사실은 응용해서 해당값이 속하는 범위를 찾을 때 많이 쓰인다. 아래 백준의 [선분 위의 점]을 풀어보면 무슨 말인지 바로 이해될텐데, 특정 값을 찾는 것이 아니라, 이 값이 리스트의 어느 범위에 속하는지를 찾는 것이다. 따라서 위의 예제 코드에서는 start>end면 그냥 none을 반환하고 종료해버렸지만, 이렇게 범위를 찾을 때는 target이 리스트에 존재하지 않을 수도 있기때문에 반환값을 달리해줘야한다.

ex) array=[1,3,5,7,9]가 있고 2가 주어졌을 때 이진탐색을 이용해서 단순 2가 있는지 없는지 유무를 찾는 것이 아니라, 2가 1,3사이에 속한다는 것을 알아내야한다는 말. 

이진탐색의 이러한 활용을 upper bound, lower bound라고 한다고 한다.

기존에는 아래와 같은 방식의 유무 만을 찾았다면, 

- array[mid] == target  ▶ return mid

- array[mid] < target  ▶ end = mid - 1

- array[mid] > target  ▶ start = mid +1

 

Lower bound는 해당 값 이상의 값이 처음 나오는 인덱스 반환하는 것(key보다 크거나 같은 첫번째 위치(이상))을 말하고,

Upper bound는 해당 값보다 큰 값이 처음 나오는 인덱스 반환하는 것(key보다 큰 첫번째 위치(초과))을 말한다. 

사실 이 개념은 이미 파이썬의 bisect left와 bisect right와 동일하다고 한다. 

그래도 이 방식을 구현하는 것을 알아보자면 아래와 같이 일반적인 이진탐색과 다르게 구현한다.

upper의 경우 target을 찾았어도 초과하는 위치를 찾아야하기 때문에 point[mid]=target이어도, start를 올린다. 그러나 lower의 경우는 target과 동일할 경우에는 구간을 줄이게 된다.

def lower_bound(start,end,target):
    while start<=end:
        mid = (start+end)//2
        if point[mid] < target:
            start = mid +1
        else:
            end = mid-1
    return start

def upper_bound(start,end,target):
    while start<=end:
        mid = (start+end)//2
        if point[mid] <= target:
            start = mid +1
        else:
            end = mid-1
    return start

[Python] 백준 #11663- 선분 위의 점

 

Lower bound & Upper bound 개념 및 구현

 

[알고리즘] 이진 탐색 심화(lower bound, upper bound)

아래 링크가 제일 설명이 와닿고 잘 정리되어 있었던 것 같다.

 

드디어! Binary Search 조건문 처리 헷갈림 해결 (+Lower Bound, Upper Bound)

 

[추가]

1. 문제에서 값을 구하라고 하는 문제 > 배열의 최댓값을 right, left=0

2. 문제에서 배열의 범위를 구하라고 하거나 배열의 범위를 기준으로 값을 구할 때 > 인덱스 값을 left,right