ASAHIネット([URL]のjouwa/salonからホットコーナー([URL] )に転載したものから。
---
　bajaさんから。
--- ここから ---
こんにちは、bajaといいます。
ちょっと面白い記事を見かけましたのでお知らせします。
古典的Binary Searchのアルゴリズムにバグがあったという話がGoogleReserch
の記事に載っていました。
実際SunのJDKのインプリも間違っていて修正されているようです。
今はプログラムの仕事はしていないので勘違いがあるかもしれませんが、サー
チをする対象の配列の数が2の30乗(10億)を超えてしまうとうまく動かない、
ということでしょうか?
それにしてもずいぶん長い間見つからなかったものですね。
--- ここまで ---

　その記事は、
[URL]
GoogleResearchのブログ
にある、
Extra, Extra - Read All About It: Nearly All Binary Searches and
Mergesorts are Broken
です。
　バグは、バイナリサーチの分割点のピボットを計算するところ
int mid =(low + high) / 2;
で、low + highがオーバーフローするってことです。
　普通これは問題にならないんです。いまのほとんどのマシンは、intが32bit
だから、このアルゴリズムで、2 ^ 31 - 1というintの最大値を超えるような
ことはないから。
　でも、著者Joshua Blochが遭遇したのは、最大値を超えた現象だったんです
ね。
　Joshua Blochさんって聞いたことあるなあと思ったら、Effective Javaの著
者ですね。Sunにいたはずなのに、Googleに移ってたんですね。調べたら、
2004年ですね。
[URL]
Joshua Bloch leaves Sun and joins Google

　なお、「Effective Java」は、Javaプログラマ必読です。参考になることは
多かったです。Effectiveシリーズはほかもなかなかよくて、ぼくは、
「Effective C++」「More Effective C++」も勉強になりました。

[URL]
ジョシュア・ブロック著、 柴田芳樹訳「Effective Java プログラミング言語
ガイド」
[URL]
Scott Meyers著、吉川邦夫訳「Effective C++ 【改訂第2版】」
[URL]
Scott Meyers著、安村通晃、飯田朱美、伊賀聡一郎訳「More Effective C++―
最新35のプログラミング技法」

　Googleは面白いこと、サイエンスをやってるから、いい人材がどんどん集ま
ってますね。ぼくが知ってるだけでも、Unix屋のRob Pike、Lisp屋のPeter
Norvigとかね。
　Microsoftは元々研究やサイエンスはやってなくて、その後Microsoft
Researchを作ったけど、やっぱ、Microsoftにお世話になりたくない人は、
Googleなんでしょう。
　Microsoftはどうしても商売ばっかり、それも独禁法違反のヤクザ会社のイ
メージがあるし(いま必死でテレビCMを流していいイメージを作ろうとしてい
ます)。Googleは大学の研究室の延長みたいな感じがしますからね。
　そんなGoogleのやり方を、単にベスト＆ブライテスト戦略だといってしまう
と底が浅いかなと。「Web進化論」はそんな臭いがぷんぷんします。^-^;

[URL]
梅田望夫著「ウェブ進化論 本当の大変化はこれから始まる」

　Peter NorvigのAIプログラミングの本には、SICPなどにあるバグの話が出て
ます。これも今回のと似た話で、みんな長い間そのまま使ってきたアルゴリズ
ムで、Norvigさんが指摘したそうです。また時間ができたら、書きますね。

　この記事に出ている「Programming Pearls」の初版は、以前、「プログラム