이분탐색 까다로운 구현 마스터하기

알고리즘 문제를 풀다 보면 자주 만나게 되는 이분탐색(Binary Search)은 개념은 단순하지만, 막상 구현하려면 생각보다 많은 함정에 빠지기 쉽습니다. 아래와 같은 경우를 다 고려해야 하기 때문이죠:

• 시작점이나 끝점을 넘어가는 경우. ex) 배열에 (3,5,7,9)가 저장되어 있는데 1을 찾음
• 답이 없는 경우. ex) 배열에 (3,5,7,9)가 저장되어 있는데 4를 찾음
• 양 끝점이 답인 경우. ex) 배열에 (3,5,7,9)가 저장되어 있는데 3을 찾음
• 배열에 숫자가 중복되는 경우. ex) 배열에 (3,3,4,4,5,5,5,7,7,9,9)가 저장되어 있는데 가장 오른쪽에 있는 5를 찾음
• 특정 수 미만, 초과, 이하, 이상인 수 찾기. ex) 배열에 (3,5,7,9)가 저장되어 있는데 5 이상인 수 중 최솟값 찾기

오늘은 이분탐색 구현 시 자주 발생하는 실수와 그 해결법에 대해 자세히 알아보겠습니다.

양 끝점 안에 답이 있는지 확인

이분탐색의 첫 단계는 탐색 범위 내에 원하는 답이 존재하는지 확인하는 것입니다. 이 과정을 생략하면 불필요한 탐색을 하거나 잘못된 결과를 반환할 수 있습니다.

문제 상황

키 순서대로 학생들이 일렬로 서 있다고 상상해 봅시다. 키가 150cm부터 180cm까지 5명의 학생이 있습니다. 여기서 키가 140cm인 학생을 찾으려 한다면 어떻게 될까요? 이분탐색 알고리즘은 중간에 있는 학생부터 확인하고, 찾는 키보다 크면 앞쪽, 작으면 뒤쪽으로 탐색 범위를 좁혀갑니다. 하지만 이 경우 아무리 찾아도 140cm인 학생은 없습니다.

만약 미리 "찾는 키가 가장 작은 학생보다 작거나, 가장 큰 학생보다 크다면 찾을 필요가 없다"는 것을 확인했다면, 불필요한 탐색 과정을 생략할 수 있었을 것입니다.

해결책

탐색 전에 간단한 경계 검사를 추가하면 됩니다. 다음 두 가지를 확인합니다:

1. 찾는 원소가 배열의 최솟값보다 작은지: 이 경우 배열에 원소가 없습니다.
2. 찾는 원소가 배열의 최댓값보다 큰지: 이 경우도 배열에 원소가 없습니다.

이처럼 탐색을 시작하기 전에 이 두 가지 경우를 확인하면, 찾는 값이 범위 밖에 있을 때 바로 결론 내릴 수 있습니다.

응용: 조건을 만족하는 값 찾기

단순히 특정 값을 찾는 것이 아니라, 어떤 조건을 만족하는 값을 찾는 문제에서도 같은 원칙이 적용됩니다. 예를 들어 "목표 시간 내에 일을 마칠 수 있는 최소 인원수"를 찾는 문제가 있다고 합시다.

이 경우에도 가능한 최소 인원수와 최대 인원수에 대해 먼저 확인해야 합니다:

• 최소 인원(1명)으로 목표 시간 내에 일을 마칠 수 있다면, 답은 1명입니다.
• 최대 인원으로도 목표 시간 내에 일을 마칠 수 없다면, 불가능한 문제입니다.

이처럼 사전 검증 단계를 통해 불필요한 연산을 줄이고 예외 상황을 미리 처리할 수 있습니다. 작은 검증 과정이지만, 이를 생략하면 알고리즘이 이상한 결과를 내거나 불필요한 연산을 수행할 수 있으니 주의해야 합니다.

시작, 끝 점 조정하기

이분탐색에서 가장 중요한 단계는 탐색 범위를 효과적으로 좁혀나가는 것입니다. 이 과정에서 시작점(left)과 끝점(right)을 적절히 조절해야 하는데, 여기서 두 가지 핵심 고려사항을 반드시 이해해야 합니다.

1. 시작점과 끝점 중 어떤 것을 조절할 것인가?

단순한 문제에서는 이 선택이 어렵지 않지만, 복잡한 문제에서는 쉽게 헷갈립니다. 이때 중앙값이 시작점과 같은 카테고리인지, 끝점과 같은 카테고리인지를 생각하면 도움이 됩니다.

예를 들어, "목표 시간 내에 일을 마칠 수 있는 최소 인원수" 문제를 살펴봅시다:

최소 인원이 1명, 최대 인원이 10명이라고 가정해 봅시다(left = 1, right = 10). 이미 10명으로 일을 마칠 수 있다는 것을 확인했습니다. 이제 중간값인 5명으로 일을 할 수 있는지 확인합니다.

• 5명으로 일을 할 수 있다면: 10명으로도, 5명으로도 일을 할 수 있습니다. 즉, 끝점과 중앙값이 같은 카테고리입니다. 더 효율적인 5명 쪽으로 탐색해야 하므로 끝점(right)을 조절합니다.
• 5명으로 일을 할 수 없다면: 10명으로는 일을 할 수 있지만 5명으로는 불가능합니다. 즉, 끝점과 중앙값이 다른 카테고리입니다. 따라서 시작점(left)을 조절해야 합니다.

이처럼 문제의 조건과 우리가 찾고자 하는 값(최소값 또는 최대값)에 따라 어떤 끝점을 움직일지 결정해야 합니다.

2. 현재 위치가 정답 후보인가, 아닌가?

이분탐색에서 단순히 mid + 1 또는 mid - 1로 끝점을 조절하면 정답 후보를 뛰어넘는 실수를 할 수 있습니다. 중요한 것은 현재 위치(mid)가 정답의 후보가 될 수 있는지 판단하는 것입니다.

• 현재 위치가 정답 후보라면: 해당 위치를 포함하도록 끝점을 조절합니다.
• 현재 위치가 정답 후보가 아니라면: 해당 위치를 제외하도록 끝점을 조절합니다.

다시 위 예시를 살펴봅시다:

• 5명으로 일을 할 수 있다면: 5명도 정답 후보입니다. 따라서 끝점을 right = mid로 설정합니다.
• 5명으로 일을 할 수 없다면: 5명은 정답 후보가 아닙니다. 따라서 시작점을 left = mid + 1로 설정합니다.

이런 방식으로 끝점을 조절하면 정답 후보를 놓치지 않고 탐색 범위를 효과적으로 좁혀나갈 수 있습니다.

버림을 하느냐, 올림을 하느냐

이분탐색에서 중간값(mid)을 계산할 때, 단순히 (left + right) / 2로 계산하면 자동으로 소수점 아래를 버리게 됩니다. 이 '버림' 연산은 대부분의 경우 문제없이 작동하지만, 가끔 무한 루프나 특정 값을 놓치는 원인이 될 수 있습니다.

무한 루프 발생 예시

배열에서 특정 조건을 만족하는 최댓값을 찾는 문제를 생각해 봅시다. 예를 들어, 배열 A에 [3, 5, 7]이 저장되어 있는데 5 이하인 수 중 최댓값을 찾는 상황입니다. 편의상 배열이 인덱스 1부터 시작한다고 가정하면 초기값은 left = 1, right = 3입니다.

1. left = 1, right=3이므로 mid=2입니다. left 값을 바꿔야 하고 A[2] = 5도 답이 될 수 있으므로 left = 2가 됩니다.
2. left = 2, right=3이므로 mid=2입니다. left 값을 바꿔야 하고 A[2] = 5도 답이 될 수 있으므로 left = 2가 됩니다.
3. left = 2, right=3이므로 mid=2입니다. left 값을 바꿔야 하고 A[2] = 5도 답이 될 수 있으므로 left = 2가 됩니다.
4. ...

이렇게 무한루프를 돌게 됩니다. 만약 올림을 이용해 중앙값을 구했다면 이야기가 달리집니다.

1. left = 1, right=3이므로 mid=2입니다. left 값을 바꿔야 하고 A[2] = 5도 답이 될 수 있으므로 left = 2가 됩니다.
2. left = 2, right=3이므로 mid=3입니다. right 값을 바꿔야 하고 A[3] = 7은 답이 될 수 없으므로 right = 2가 됩니다.
3. left = right이므로 이 지점이 정답입니다.

버림과 올림 선택 기준

버림과 올림 중 어떤 것을 선택할지는 탐색 범위를 좁히는 방식에 따라 결정됩니다:

1. 버림을 사용해야 하는 경우:
   • left = mid + 1 그리고 right = mid로 업데이트하는 경우
   • mid = (left + right) / 2
2. 올림을 사용해야 하는 경우:
   • left = mid 그리고 right = mid - 1로 업데이트하는 경우
   • mid = (left + right + 1) / 2

결론

이분탐색에서 중간값 계산 방식은 탐색 범위 업데이트 방식과 밀접하게 연관되어 있습니다. 특히 left = mid로 업데이트하는 경우 올림을 사용해야 무한 루프를 방지할 수 있습니다. 이를 기억하면 이분탐색 구현 시 발생할 수 있는 많은 실수를 피할 수 있습니다.