이진탐색

종이를 접듯이 탐색 범위를 반씩 좁혀나감으로써 $O(logN)$의 시간복잡도 내에 탐색을 마칠 수 있는 사기적인 탐색 방법!

 

오늘은 이진탐색에 꽂혀서 하루 종일 이진탐색 세 문제를 풀었다. 푼 문제 수는 적지만 많은 깨달음을 얻었기 때문에 오히려 좋아. 오늘 알게 된 사실은 아래와 같다.

 

1. 이진탐색의 기본적인 틀은 아래와 같다.

 

int start = s, end = e;
while (start <= end) {
  int mid = (start + end) / 2;
  if (mid < target)
    start = mid + 1;
  else if (mid > target)
    end = mid - 1;
  else {
    ans = mid;
    break;
  }
}

 

2. 꼭 mid가 target보다 클 때, 작을 때, 같을 때로 나누지 않고, 클 때, 작거나 같을 때와 같이 유연하게 나눌 수 있다.

 

예를 들어 target보다 작은 수 중에 가장 큰 수를 찾고 싶다면 클 때와 작거나 같을 때로 나누고, 작거나 같을 때마다 mid 값을 저장하면 된다.

 

분기를 나누는 팁은 범위가 어떻게 움직이는지 예상해보는 것이다. 범위는 항상 mid를 기준으로 작은 쪽 또는 큰 쪽으로 움직인다. 만약에 클 때와 작거나 같을 때로 나누었다면 mid가 target과 같을 때마다 그보다 큰 범위를 탐색하므로 최종적으로 start = end = mid가 되는 지점은 target보다 작은 수들 중에서 가장 큰 수 또는 target 둘 중 하나다.