이분탐색과 Python의 bisect

이분 탐색(Binary search)

이분 탐색을 사용할 때는 반드시 오름차순으로 정렬이 되어있어야 합니다!

 

이분 탐색은 이름처럼 주어진 범위를 반으로 나눠가면서 탐색하는 방법이다. 1~n까지 수 또는 리스트에서 특정 수 a를 찾는다고 하면 우리는 1~n까지 모두 탐색하여 x가 있는지 찾는 방법이 있다. 이 방법은 시간 복잡도 O(n)으로 n이 커질수록 x값을 찾는데 시간이 오래 걸린다. 이때 시간 복잡도를 O(logn)으로 줄여 탐색할 수 있는 방법이 바로 이분 탐색이다.

알고리즘

1. 탐색하고자 하는 값의 범위 또는 리스트에 중복되는 값이 없는 경우

index	0	1	2	3	4	5	6	7	8
value	0	1	2	3	4	5	6	7	8

이분 탐색은 left, right로 mid값을 구하고, mid값을 기준으로 찾고자 하는 수 n과 대소를 비교하며 범위를 줄여나가며 값을 찾는다. x가 현재 mid값보다 작다면 right를 mid-1로 옮기고, x가 mid값보다 크다면 left를 mid+1로 옮긴 후 mid값을 (left + right)/2로 설정한다. 이 과정을 반복하며 범위를 줄여나가고 left와 right가 같아지면 탐색을 중단한다. 만약 mid값이 x와 같다면 x를 또는 x의 인덱스를 반환하고, x와 mid값이 다르면 -1을 반환한다. 

코드

#0~n 중에서 x값을 찾는 경우(리스트x)
#리스트에서 값을 찾는 경우 조건문의 mid를 list[mid]로 변경해서 사용

left = 0
right = n

while left <= right:
    mid = (left + right) // 2
    if mid < x:
        left = mid + 1
    elif mid > x:
        right = mid - 1
    else: # mid == x
        break

if mid == x:
    print(mid)
else:
    print(-1)

2. 탐색하는 범위에 중복 값이 있는 경우

index	0	1	2	3	4	5	6	7	8
value	0	1	1	2	2	2	2	3	3

만약 우리가 탐색하는 범위에 중복된 값이 저장되어 있는 경우 어떻게 찾을 수 있을까? 단지 배열 안에 찾고자 하는 x값이 있는지 확인하는 경우라면 위와 같은 이분 탐색 알고리즘을 사용해도 무방하다. 하지만 알고리즘 문제를 풀다 보면 찾고자 하는 값의 가장 첫 번째 인덱스, 찾고자 하는 값의 마지막 인덱스 또는 찾고자 하는 값의 다음 인덱스를 찾아야 하는 경우가 있다. 이때 사용할 수 있는 것이 lower bound와 upper bound이다. python에서는 bisect모듈의 bisect_left와 bisect_right를 이용하면 필요한 인덱스를 구할 수 있다.

 

- bisect.bisect_left

 

lower_bound는 우리가 찾고자 하는 값의 첫 번째 인덱스를 반환하며, python에서는 bisect.bisect_left()를 사용하여 찾을 수 있다. 위 예제에서 우리가 2를 찾고자 할 때 bisect.bisect_left()를 사용하면 인덱스 3이 반환된다.

bisect.bisect_left(a, x, lo, hi)

a : 배열
x : 찾고자 하는 값
lo, hi : 배열의 범위를 지정하는 값(지정하지 않은 경우 배열 전체 탐색 <lo = 0, hi = len(a)>)
lo = 배열의 시작 범위
hi = 배열의 끝 범위

 

- bisect.bisect_right

 

upper_bound는 우리가 찾고자 하는 값보다 큰 수중에서 가장 작은 인덱스를 반환하며, python에서는 bisect.bisect_right()를 사용하여 찾을 수 있다. 즉, 다음 값의 인덱스를 반환한다고 생각하면 된다. 위 예제에서 bisect.bisect_right()를 사용하면 찾고자 하는 값 2보다 큰 수중에서 가장 작은 인덱스 7을 반환한다. 

bisect.bisect_right(a, x, lo, hi)

a : 배열
x : 찾고자 하는 값
lo, hi : 배열의 범위를 지정하는 값(지정하지 않는 경우 배열 전체 탐색 <lo = 0, hi = len(a)>)
lo = 배열의 시작 범위
hi = 배열의 끝 범위

---

이분탐색 문제

[16434] 드래곤 던전 :https://www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

풀이

https://lkitty0302.tistory.com/4

BOJ :: [16434] 드래곤 앤 던전

[1654] 랜선자르기 : https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

풀이

-

 

작성한 글에 잘못된 부분이나 문제가 있는 경우 댓글에 작성해 주시면 수정하도록 하겠습니다. 질문도 환영합니다! :)