0802 bug of binary search

바이너리서치 자체에 버그가 있다는 말은 아니고, 해당 알고리즘의 구현에 문제가 있다는 얘기. 해커뉴스 페북에 떠서 읽게 됨. 원문은 구글 리서치 블로그. 원제(‘Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken’)가 너무 거창해서 눈 크게 뜨고 읽었지만, 소문난 잔치에 먹을것 없더라.

int mid =(low + high) / 2;

이 부분에서 overflow가 날 수 있다는게 주 내용

아래와 같이 해결.

int mid = (low + high) >>> 1;

C/C++과 달리 unsigned right shift operator가 없는 언어에서는

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

그나저나 글쓴이가 Jon Bentley의 수업을 직접 들었다니 그점이 제일 부럽다. 어렵지 않은 내용을 누구에게 배우느냐는 배움 자체만으로는 그렇게 중요하지 않을 수 있지만, 그래도 명사로부터 배우는건 기분이라도 좋은듯.

그리고 아래와 같이 하면 어떤가 생각해보니

mid = low/2 + high/2

integer연산이라 round off때문에 한가운데가 아니라 mid-1이 걸릴 수 있다.