이분탐색 구현 팁 및 반환값 줄이기(부제: 공부하며 정리하는 생각들)

공부하면서 참조한 자료

1.종만북

2.

https://blog.naver.com/jinhan814/222156334908

이분 탐색, 파라메트릭 서치 안 헷갈리는 TIP

 

이분탐색은 문제에서 주어지는 탐색 값의 기준을 찾는 것이 문제이다.

예를 들어 1부터 10억cm의 길이의 자를 분할해서 최소 5개의 개수로 나누고 싶은데 이 때 "분할하는 경우에 가장 큰 분할 길이를 구하시오" 같은 문제에서 분할하는 길이를 구하면 되는 문제이다. 알고리즘에 관련된 설명과 강의는 나보다 뛰어나신 분도 너무 많고 작성하시는 분도 너무 많기에 넘어가고 이분탐색을 구현할 때 구현의 팁을 작성해보자고 한다.

 

이분 탐색의 구현 순서.

1. 입력값 받기

2.while(left + 1 < right)틀의 이분탐색 반복문 작성하기

3.left와 right중 어떤 것을 옮길지에 대한 check()함수 작성하기

 

원래 나는 2번의 반복문 구현하기를 while(left <= right)  형식으로 작성하였다. 그러면 구현 내부문이

while(left <= right)
{
    ll mid = (left + right) / 2;
    
    if(check())
        left = mid + 1;
    else
        right = mid - 1
}

while(left + 1 < right)
{
    ll mid = (left + right) / 2;
    
    if(check())
        left = mid;
    else
        right = mid
}

이런 식으로 변경이 가능하다. 이렇게 변경하는 이유는 결과 반환 값을 left와 right 둘 중 하나로 줄여서 위에서 말한 오류를 줄일 수 있기 때문이다. left와 right 둘 중 어떤 것을 반환하는지에 대한 것은 문제의 설명을 읽고 이것이 upper_bound에 관한 특징인지 lower_bound에 관한 특징을 가지는지 알아야 한다.

upper_bound는 v[i - 1] <= mid <v[i]의 특징을 가지고 있고 lower_bound는 v[i] < mid <=v[i]의 특징을 가지고 있다.

 

내가 문제를 풀 때 세운 규칙은 upper_bound의 특징을 가지고 있는 경우라면 문제는 최소의 경우를 구하라는 문제이고 이 경우에는 right를 반환하는 것이고 lower_bound의 특징을 가지고 있는 경우라면 문제는 최대의 경우를 구하는 문제고 left를 반환한다라고 규칙을 세웠다.. 이러한 이유는 upper_bound는 v[i - 1] <= mid의 범위를 가진다. 그렇기 때문에 while(left + 1 < right)의 조건이 성립하지 않으면서 이분탐색을 탈출하는 경우에 left = mid 값으로 변경이 일어나고 left + 1 값이 mid값과 겹치는 순간이므로 right값이 탐색 기준 왼쪽 위치에 위치한다. 마치 왼쪽 주먹이 left이고 오른쪽 주먹이 right라면 왼쪽 주먹이 오른쪽 주먹 뒤로 오게 되는 순간 탐색이 종료되는 것이다.(이러면 Right가 반대로 탐색의 시작 위치이므로 최솟값이다.)

 

위의 미흡한 설명으로 이해가 안 간다면 아래의 코드를 예시로 들어보겠다.

ll upper_boundvector<ll>& v, int x) 
{
    ll left = 0;
    ll right = LLONG_MAX;   
    while (left + 1 < right)
    {
        ll mid = (left + right) / 2;
        //밑에 비교 연산자가 <=면 right반환
        if (v[mid] <= x)
            left = mid;
        else 
            right = mid;
    }
    return right;
}

 

정리하자면 upper_bound함수에서 If의 비교 연산자가 "<=" 라면 right 반환 "<"라면 left 반환이다.