0802 bug of binary search - 편집 역사

2017년 8월 2일 (수) 02:18에 Admin님의 편집

2017-08-02T02:18:33Z

2017년 8월 2일 (수) 02:17에 Admin님의 편집

2017-08-02T02:17:37Z

2017년 8월 2일 (수) 02:17에 Admin님의 편집

2017-08-02T02:17:25Z

Admin: 새 문서: 바이너리서치 자체에 버그가 있다는 말은 아니고, 해당 알고리즘의 구현에 문제가 있다는 얘기. [https://www.facebook.com/hnbot/posts/1438121402909803...

2017-08-02T02:12:58Z

새 문서: 바이너리서치 자체에 버그가 있다는 말은 아니고, 해당 알고리즘의 구현에 문제가 있다는 얘기. [https://www.facebook.com/hnbot/posts/1438121402909803...

새 문서

바이너리서치 자체에 버그가 있다는 말은 아니고, 해당 알고리즘의 구현에 문제가 있다는 얘기. [https://www.facebook.com/hnbot/posts/1438121402909803 해커뉴스 페북]에 떠서 읽게 됨. [https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html 원문]은 구글 리서치 블로그.

← 이전 판		2017년 8월 2일 (수) 02:18 판
1번째 줄:		1번째 줄:
−	바이너리서치 자체에 버그가 있다는 말은 아니고, 해당 알고리즘의 구현에 문제가 있다는 얘기. [https://www.facebook.com/hnbot/posts/1438121402909803 해커뉴스 페북]에 떠서 읽게 됨. [https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html 원문]은 구글 리서치 블로그.	+	바이너리서치 자체에 버그가 있다는 말은 아니고, 해당 알고리즘의 구현에 문제가 있다는 얘기. [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;		int mid =(low + high) / 2;

@@ 13번째 줄: / 13번째 줄: @@
 그리고 아래와 같이 하면 어떤가 생각해보니
   mid = low/2 + high/2
-integer연산이라 round off때문에 한가운데가 아니라 그 mid-1이 걸릴 수 있다.
+integer연산이라 round off때문에 한가운데가 아니라 mid-1이 걸릴 수 있다.
 <disqus/>

← 이전 판		2017년 8월 2일 (수) 02:17 판
1번째 줄:		1번째 줄:
	바이너리서치 자체에 버그가 있다는 말은 아니고, 해당 알고리즘의 구현에 문제가 있다는 얘기. [https://www.facebook.com/hnbot/posts/1438121402909803 해커뉴스 페북]에 떠서 읽게 됨. [https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html 원문]은 구글 리서치 블로그.		바이너리서치 자체에 버그가 있다는 말은 아니고, 해당 알고리즘의 구현에 문제가 있다는 얘기. [https://www.facebook.com/hnbot/posts/1438121402909803 해커뉴스 페북]에 떠서 읽게 됨. [https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html 원문]은 구글 리서치 블로그.
		+
		+	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/>