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

public int binarySearch(int[] a, int key) {

	int low = 0;
	int high = a.length - 1;

	 while (low <= high) {

	       int mid = (low + high) / 2;

	       int midVal = a[mid];
	
	       if (midVal < key)
	           low = mid + 1;
	       else if (midVal > key)
	           high = mid - 1;
	       else
	           return mid; // key found

	 }

	 return -(low + 1);  // key not found

}

위의 코드가 저도 알고 여러분도 아는 가장 대중적인 이진탐색(binary search) 코드입니다. 

위의 코드에는 치명적인 버그가 하나 있는데요, 눈치채셨나요?

네, 맞습니다 6번째 줄의 int mid = (low + high) / 2

바로 이 부분입니다.

(low+high)가 int 범위(2³¹ - 1)를 넘어서는 순간 문제가 발생하게 되는데요,

이 합이 오버플로우되면서 음수값으로 변하게 되고 결국 합을 2로 나눈 몫도 음수값으로 나오게 되는것이죠.

이렇게 되면 제대로 된 반환값을 도출해내는건 기대하기 어렵습니다.

그럼 버그를 잡기 위해서는 어떻게 해야 할까요?

당연히, 오버플로우가 생기지 않게 해야합니다. 

int mid = low + ((high - low) / 2);

간결하면서도 창의적인 해결방법입니다. 

 연산의 어느 과정에서도 오버플로우가 나지않으면서도 원하는 결과를 얻을 수 있는 방법이죠.

이러한 문제점은 이진탐색에서 뿐만아니라 병합정렬(merge sort)을 포함해 모든 분할정복(divide & conquer) 방식의 알고리즘에서 조심해야 할 점입니다.

이제 분할정복 알고리즘을 구현할 때 가장 빈번히 나오는 버그를 고쳤습니다. 

여기서 얻을 수 있는 교훈은 엄청 간단해보이는 코드에서도 우리는 버그에서 자유로울 수 없다는 겁니다. 

버그에서 더 자유로운 프로그램을 만들기 위해서 우리는 철저한 설계, 테스트 과정, 정형기법(formal method), 코드 리뷰, 정적 분석들을 사용합니다. 

이 모든 방법과 함께 코드를 작성하더라도 코드는 항상 존재해왔습니다. 

즉, 겸손함을 가지고 항상 신중하게, 방어적으로 코딩하는 습관을 들이는 것이 필요하겠습니다.