[알고리즘/이분탐색/BinarySearch] 왜 left+(right-left)/2는 overflow가 발생하지 않을까?

 

 

 

LeetCode에서 이분 탐색(Binary Search) 문제를 풀고 있는데 아무리 생각해도 굉장히 간단한 이분 탐색 문제로 쉽게 풀릴 거 같은데

계속 overflow가 발생해서 runtime error가 발생했다. 그래서 다른 사람의 코드를 확인해봤는데 문제는 바로

int mid = (left + right) / 2;

이 부분에 있었다. 여기서 계속 overflow가 발생했던 것인데 다른 사람들은 

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

이렇게 사용하는 것이 아닌가!

대체 왜 이렇게 사용하면 overflow가 발생하지 않고 잘되는지 열심히 구글링하며 영어 해석하며 찾아봤다.

 

 

---

 

우선 저 오버플로우가 발생하는 원인에 대해서 알아보자.

int mid = (left + right) / 2;

위의 코드는 left와 right의 평균 값인 mid(가장 가까운 정수)를 구하기 위한 것인데, 이렇게 하면 올바른 것처럼 보이지만 int변수인 left와 right의 큰 값에 대해서는 실패하게 된다.

특히, left와 right의 합이 int의 max value인 (2^31 - 1)보다 크다면 문제가 된다. 그 합이 오버플로우 되어 음수가 된다.

 

 

이를 해결하기 위한 방법은 아래와 같다.

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

//2
int mid = (left + right) >>> 1;

//3
int mid = ((unsigned int)left + (unsigned int)right)) >> 1;

 

---

 

그러니까 여기서 문제는 left + right가 int의 max value보다 큰 것인데, max value를 넘어가지 않게만 하면 되는 것 아닐까?

헷갈릴 때는 예제를 만들어서 직접 해보는게 최고다^^!

left = 997
right = 999

left + right = 1995                       //(left+right)/2를 해야되는데 sum에서 overflow가 발생

right - left = 2                          //right와 left 사이 개수
(right - left) / 2 = 1                    //right와 left 사이 개수의 절반   
left + (right - left) / 2 = 997 + 1 = 998 //개수 절반을 left에서 더하면 중간값 등장~

 

한번 더 해보자~

int max value = 5 라고 가정하고 해 보자!

1 2 3 4 5                                   //integer max value = 5

//1
int mid = (left + right) / 2                //6(overflow)/2 = 3
//2
int mid = left + (right - left) / 2         //1+4/2 = 3


left = mid + 1                              //left = 4, right = 5
//1
mid = (left + right) / 2                    //9(overflow)/2 = 4
//2
mid = left + (right - left)/2               //4 + 1/2 = 4

결과는 같은데 2의 경우 오버플로우가 발생하지 않았다. 

 

 

---

✍️ Conclusion

 

찾아보니까 생각보다 간단한 수학 문제였다...!

right - left = 사이 값 개수

(right - left) / 2 = 개수 절반

left + (right - left) / 2 = 중간값 도출

재미있는 알고리즘~

 

 

 

 

 

 

[참고]

https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

https://stackoverflow.com/questions/27167943/why-leftright-left-2-will-not-overflow

why left+(right-left)/2 will not overflow?