C 언어 이진 검색에서 2의 30승 이상의 원소일 때 mid 값 오버플로우 줄이기

 

이진 검색에서 2의 30승 이상의 원소일 때 mid 값 오버플로우 줄이기

 

정리. 오상문 sualchi@daum.net

 

 

이진 검색(Binary Search)에서 원소 개수가 2의 30승(10억7천3백7십4만1천8백2십3개)를 넘어가면 mid 값 오버플로우가 발생할 수 있다.

일반적으로 mid 값을 얻는 코드는 다음과 같다. (참고로 low, high 데이터형은 signed int이다.)

 

int mid = (low + high) / 2;

 

그런데, 오버플로우 발생 시점을 그 두 배로 높이려면(20억개 수준으로) 다음처럼 코드를 작성하면 됩니다.

 

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

 

또는 다음처럼 형변환과 쉬프트 연산자를 이용하는 방식도 가능하다. (우측 쉬프트 연산자는 2로 나누는 효과가 있음)

 

2) int mid = ((unsigned int)low + (unsigned int)high)) >> 1

 

C#의 Array.BinarySearch에서는 1)과 2)를 혼용한 코드를 사용한다.

 

private static int GetMedian(int low, int hi)

{

return ( low + ((hi - low) >> 1))

}

 

C 언어 사용자라면 다음과 같은 함수를 이용하면 된다.

(단, 운영체제에 따라서 int 형의 크기가 달라질 수 있다.)

 

int GetMedian(int low, int hi)

{

return ( low + ((hi - low) >> 1))

}

 

좀더 자세한 내용은 아래 링크를 참고하기 바란다.

 

http://blog.naver.com/techshare/220777340087