오버플로우 방지 중간값 계산 (overflow-safe midpoint calculation)

 

📌 이전 방식 : (left + right) / 2

보통 중간값을 계산할때 다음과 같은 수식을 사용한다.

이때 left와 right값이 매우 큰 경우, 두 값을 더하는 과정에서 정수 오버플로우가 발생할 수 있다.

int mid = (left + right) / 2;

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

System.out.println(mid); //-2 : 오버플로우로 인해 잘못된 값 반환

 

 

📌 개선 방식 : left + (right - left) / 2

따라서 다음과 같이 개선한다.

1. (left - right)는 항상 right와 left의 차이이므로 오버플로우가 발생하지 않는다.

2. (right - left) / 2는 탐색 범위의 절반만큼 더하거나 빼는 값을 계산한다.

3. left + (right - left) / 2는 left로부터 탐색 범위의 절반만큼 이동한 값을 의미한다.

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

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

System.out.println(mid); //2147483646

 

 

💡 수식

 

 

✅ 정리

int 자료형 범위 : −2,147,483,648 ~ 2,147,483,647

대략 자료형 범위를 넘어가는 억단위 대규모 데이터를 처리할때는 유용할 것 같다.