이 포스팅은 백준 내 질문검색을 돌아다니다가 palilo님의 글을 보고 정리하게되었습니다.
이분탐색이 필요하거나 사용되는 경우
💡 case 1. 어떤 f(x)
를 만족하는 x
의 최솟값을 찾는 경우
💡 case 2. 어떤 f(x)
를 만족하는 x
의 최댓값을 찾는 경우
우선 이분탐색의 기본 조건은 찾고자 하는 자료구조가 오름차순 정렬되어있어야 한다. 정렬된 배열이 있다고 가정을 해보면 왼쪽 부분을 사용할 건지 오른쪽 부분을 사용할 건지 먼저 정하고 시작을 해야한다.
L-M
/ L-(M-1)
(M+1)-R
/ M_R
왼쪽 부분을 사용한다면 최솟값을 찾기에 용이할 것으로 보인다. 왜냐하면 같은 값이 존재해도 왼쪽부분으로 해당하면 최소 index를 찾을 수 있기 때문인데 예를 들면 아래 그림과 같다.
확인된 f(M) 값이 target보다 크거나 같으면 R값을 M으로 설정해준다. 그렇게 되면 L부터 M까지의 크기가 더 크게 설정되기 때문에 M - 1값으로 설정하지 않는다. 이때 M 값은 (L + R) >> 1
로 사용한다. (비트연산)
반대로 f(M) 값이 target보다 작으면 어떻게 해야할까? L은 곧 찾는 범위의 시작점을 의미하기 때문에 L을 M + 1 땡겨준다. 이를 코드로 구현하면 다음과 같다.
left, right = min, max + 1
while left != right:
mid = (left + right) // 2
if f(mid) == True:
right = mid
else: left = mid + 1
if left == max + 1: return IMPOSSIBLE
return left
반대로 오른쪽 부분을 사용한다면 최댓값을 찾기에 용이할 것으로 보인다. 왜냐하면 같은 값이 존재해도 오른쪽 부분을 계속 유지한다면 최대 index를 찾을 수 있기 때문이다.
그림처럼 찾는 값인 target은 오른쪽 부분에 위치해야 최댓값이 나오기 때문에 여기서 M 값을 구할때는 최솟값과는 다르게 (L + R + 1) >> 1
를 해준다. 이유는 아래 그림을 보면 알 수 있다.
L을 초기화해줄 때 M으로 하기 때문에 이와 같이 f(M)
이 참인 경우에는 무한루프가 돌게 된다. 무한루프를 방지하기 위해서 +1
을 해줘야 한다. 만약에 +1
을 해주지 않았더라면 최댓값을 찾는 과정에서 M의 변화가 아래와 같이 이루어졌을 것이다.
index | 1번째 | 2번째 | 3번째 | 4번째 | 5번째 | 6번째 | ... |
---|---|---|---|---|---|---|---|
M | 4 | 1 | 2 | 2 | 2 | 2 | 2 |
결국에 모든 경우의 수에서 L-M과 M-R 배열의 크기를 균일하게 맞춰주기 위해서 +1
이 필요하다. 그렇지 않으면 무한루프에 빠지게 된다.
left, right = min - 1, max
while left != right:
mid = (left + right + 1) // 2
if f(mid) == True:
left = mid
else: right = mid - 1
if left == min - 1: return IMPOSSIBLE
return left
개인적으로 정리하면서 규칙(?)을 찾아봤는데,
최솟값을 찾을 때에는 왼쪽 배열의 크기가 큰 것이 유리하므로 f(M)가 참일 때 R을 M으로 초기화해준다.
최댓값을 찾을 때에는 오른쪽 배열의 크기가 큰 것이 유리하므로 f(M)가 참일 때 L을 M으로 초기화해준다.
각 -1
을 해주는 부분은 f(M)이 거짓일 때 해주는 것.
그리고 주의해야할 점은 최댓값을 찾을 때 M을 설정해주는 방식이 (L + R + 1) >> 1
이란 점