[이진 탐색] int mid = left + (right - left) / 2;

이진 탐색은 정렬된 배열에서 특정 값을 빠르게 찾기 위한 알고리즘이다. 매 반복마다 검색 범위를 반으로 줄이는 과정에서 중간 인덱스(mid)를 계산을 단순하게 (left + right) / 2를 사용하면 오버플로우의 위험이 존재한다.

결론만 먼저 말하면, int mid = left + (right - left) / 2; 방식을 권장한다.

---

1. 기본적인 중간 인덱스 mid 계산 방식

이진 탐색에서는 검색 범위의 양 끝 인덱스인 left와 right를 기반으로 중간 인덱스를 계산한다.

int mid = (left + right) / 2;

이 방식은 간단하지만, left와 right가 매우 큰 값일 경우 오버플로우가 발생할 수 있다.

---

2. 오버플로우

오버플로우는 프로그래밍 언어에서 변수에 할당된 메모리 범위를 초과하여 값이 표현될 때 발생한다.

예를 들어, int 타입은 일반적으로 -2,147,483,648부터 2,147,483,647까지의 값을 표현할 수 있는데,
만약 left와 right가 모두 큰 값이면, 이 두 값을 더하는 과정에서 이 범위를 넘어갈 수 있다.

 

예를 들어, left = 2,000,000,000이고 right = 2,000,000,010인 극단적인 상황을 가정해보면,

• (left + right)의 값은 4,000,000,010이 되고, 이는 int 타입이 표현할 수 있는 최대값 2,147,483,647를 훨씬 초과한다.
• 이런 경우, 잘못된 계산이 되어 올바른 mid 값이 도출되지 않으며, 예외 상황이 발생할 수 있다.

---

3. 개선된 mid 계산 방식: left + (right - left) / 2

이 문제를 해결하기 위해 사용하는 방식이 바로 아래와 같다.

int mid = left + (right - left) / 2;

• (right - left): 이 값은 항상 배열 내의 범위를 나타내며, 오버플로우가 발생할 위험이 매우 낮다.
• left + ...: left 값에 (right - left)의 절반 값을 더하므로, 실제 중간 인덱스를 안전하게 계산할 수 있다.

즉, 두 인덱스의 합을 직접 계산하지 않기 때문에, 두 값이 크더라도 오버플로우 발생 가능성을 효과적으로 줄일 수 있다.

 

정리

이진 탐색에서 중간 인덱스를 계산할 때, 단순히 (left + right) / 2를 사용하는 방식은 오버플로우의 위험이 존재한다.

int mid = left + (right - left) / 2; 방식을 이용하면 보다 안정적인 코드 작성을 할 수 있다.