이분 탐색 알고리즘 헷갈리는 내용 정리(while 조건, lo/hi 갱신 처리, 반환 값, lo/hi 범위)

이분 탐색을 이용한 백준 문제들을 풀다가 헷갈리는 부분들이 생겨 그에 관해 정리해본다.
일단 이분 탐색 알고리즘의 대표적인 코드를 한번 보자.

int BinarySearch(int lo, int hi, int target)
{
    while(lo + 1 < hi)
    {
        int mid = (lo + hi) / 2;
 
        if(arr[mid] <= target)
            lo = mid;
 
        else if(arr[mid] > target)
            hi = mid;
    }
    return lo;
}

여기서 헷갈리는 부분들이 4가지가 있었다.

1. while문 안의 조건
   다른 사람들의 이분 탐색 코드를 살펴보면, 대표적으로 많이 쓰이는 3가지가 있다. (lo + 1 < hi), (lo < hi), (lo <= hi) 이다.
   어떨 때 어떤 것을 써야하는 지 조건이 있을 줄 알았는데 아니었다. 어떤 조건을 선택할지는 본인의 취향이다.
   다만, 이 조건을 어떤 것을 선택하느냐에 따라 while문 내부의 내용들이 다 달라진다.
2. lo/hi 갱신 처리
   (lo + 1 < hi) 조건을 사용하면 while문 내부에서는 항상 lo와 hi 사이에 1개 이상의 원소가 있다.
   즉, lo = mid 혹은 hi = mid로 lo와 hi를 갱신하여도 무한 루프를 돌 일이 없다.
   (lo < hi) 조건을 사용하면 lo == hi가 되는 순간 while문을 탈출한다. while문을 탈출하기 직전의 상황을 보자.
   lo와 hi 사이에 원소가 없이 서로 붙어 있는 상황인데, lo = mid 혹은 hi = mid로 갱신을 할 경우 while문을 탈출하지 못하는 무한 루프에 빠지게 된다.
   그러므로 lo = mid + 1 혹은 hi = mid로 갱신한다.
   (lo <= hi) 조건을 사용하면 lo > hi가 되는 순간 while문을 탈출한다. while문을 탈출하기 직전의 상황은 lo == hi이다.
   그러므로 lo = mid + 1 혹은 hi = mid - 1로 갱신하여야 무한 루프에 빠지지 않는다.
3. 반환 값
   (lo + 1 < hi) 조건을 이용한다고 하자. 다른 조건에서도 원리는 같다.
   arr[mid] >= target 라면, hi = mid로 갱신을 해줘야한다.
   while문을 탈출하는 lo + 1 == hi의 경우에, hi = target이 되므로 hi 값을 반환해준다.
   arr[mid] <= target 라면, lo = mid로 갱신을 해줘야한다.
   while문을 탈출하는 lo + 1 == hi의 경우에, lo = target이 되므로 lo 값을 반환해준다.
   값을 찾는 조건에 따라 반환 값이 달라지는데, 이분 탐색 과정이 진행됨에 따라 target 값에 가까워지는 것이 무엇인지 생각하면 쉽게 반환 값을 찾아낼 수 있다.
4. lo/hi 범위
   (lo + 1 < hi) 조건을 이용한다고 하자.
   문제에서 target이 있을 수 있는 범위가 min <= target <= max로 주어졌다고 하자.
   arr[mid] >= target 일 때, hi = mid로 갱신하는 방식으로 target을 찾는다고 하자.
   답이 되는 hi는 min부터 max까지의 범위에 존재할 수 있다.
   while문 내에서는 항상 lo + 1 < hi를 만족하고, 탈출했을 때는 lo + 1 == hi여야한다. 그러므로 초기에 lo = min - 1, hi = max로 설정해줘야 올바르게 탐색할 수 있다.
   arr[mid] <= target 일 때, lo = mid로 갱신하는 방식으로 target을 찾는다고 하자.
   답이 되는 lo는 min부터 max까지의 범위에 존재할 수 있다.
   while문 내에서는 항상 lo + 1 < hi를 만족하고, 탈출했을 때는 lo + 1 == hi여야한다. 그러므로 초기에 lo = min, hi = max + 1로 설정해주어야 올바르게 탐색할 수 있다.

---