이진 탐색

개론

이론

이진 탐색 알고리즘은 오름차순으로 정렬된(선형적인) 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 전체 데이터 리스트에서 중간에 해당하는 값을 임의의 값으로 선택하여, 그 값이 찾고자하는 값보다 크고 작음을 확인하여 다음 탐색여부를 결정하는 방식이다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값이 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 이 것을 계속 반복하다보면 최고값을 나타나는 값과 최소값이 역전되는 상황이 발생하고 탐색이 종료된다. 이 방식은 퀵소트의 피봇과도 유사함을 볼 수 있다. 이 방식은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 그것만 보장된다면 완전탐색의 속도보다 속도가 훨씬 빠르다는 장점이 있다.

원리

잠시동안만 퀵소트의 원리는 잊어두자. 그래야 헷갈리지 않는다. 가장 중요한 변수는 left와 right, mid이다. 매 구간당 반복되어 탐색할 구간들을 가리키는 값이다. Mid는 left와 right의 중간값이고 가장 core로직은 단순히 이 mid값이 찾고자 하는 값보다 큰지 작은지만 구별하는 것이다. 만약 mid값이 더 크다면 right를 mid까지 당겨서 탐색구간을 좁히고, 반대의 경우에는 left를 mid까지 당겨서 탐색구간을 좁힌다. 탐색 리스트의 배열이 정수이며 오름차순이라는 것이 보장된다면 결국 이 과정들을 반복했을 때 반드시 원하는 값을 얻을 수 있다.

구현

이진 탐색의 기본적인 형태는 다음과 같다.

long long left = 0;
long long right = 최초값;
long long mid = 0;

while (left < right)
{

mid = (left + right) / 2;



    if (height >= M) // left갱신 조건이라면
    {
        left = mid;

    }
    Else // right갱신 조건이라면
    {
        right = mid - 1;
    }
}

위는 가장 기본적인 형태의 이진 탐색 코드이다. 탐색의 대상이 되는 mid를 원하는 결과와 비교하여 left나 right를 갱신한다. 한가지 조심해야 할 것이있다. 원하는 값 범위의 최소값을 구할 것이냐, 최대값을 구할 것이냐에 대한 것으로, 문제가 되는 부분은 left, right값을 갱신함에 있어서 둘 사이의 간격이 1밖에 되지 않으며, 계속 left값만 갱신하는 상황에 도달하면 mid = (left+right)/2의 계산이 항상 같은 값을 가지게 될 것이라는 것이다. 이럴 때는 다른 조치를 취해야 하는데, 만약 left와 right의 간격이 1을 유지할 경우 mid를 갱신하는 로직이 mid = (left+right+1)/2로 바뀌어야 한다는 점이다. 이를 반영하면 다음과 같다.

long long left = 0;
long long right = 최초값;
long long mid = 0;

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


    if (height >= M) // left갱신 조건이라면
    {
        left = mid;

    }
    Else // right갱신 조건이라면
    {
        right = mid - 1;
    }
}