0802 bug of binary search 문서 원본 보기

바이너리서치 자체에 버그가 있다는 말은 아니고, 해당 알고리즘의 구현에 문제가 있다는 얘기. [https://www.facebook.com/hnbot/posts/1438121402909803 해커뉴스  페북]에 떠서 읽게 됨. [https://research.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’)가 너무 거창해서 눈 크게 뜨고 읽었지만, 소문난 잔치에 먹을것 없더라.

 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이 걸릴 수 있다.

<disqus/>