Donald Knuth（彼の本を読んでいないことで知られる）は、最初のバイナリ検索は1946年に公開されましたが、 バグのない最初のバイナリ検索は1962年にのみ公開されたと書いています。
バイナリ検索アルゴリズムは、辞書で単語を検索する方法に似ています。 辞書を中央で開き、必要な単語の半分を探します。 最初に言ってみましょう。 正しい単語が見つかるまで、最初の部分を中央で開き、半分まで続けます。
このような配列の場合：順序付けられた配列があり、目的の配列と比較して配列の中央から数値を取得します。 それが多いことが判明した場合、配列の前半の目的の数、少ない場合-後半の。 目的の数が見つかったら残りの半分を分割し続け、そのインデックスを返します。見つからない場合はnullを返します。
この問題は、プログラマーの10％しか解決できないと主張しています。 はい、できません！ ここに吸盤があり、私は、Firebugに5分ほど充電したと思った...そして、非稼働バージョンは準備ができている。 別のイテレーションなど。 合計で1時間半、最終的な解決策はまだ2つのエラーです。 恥を知れ！
バイナリ検索を作成したことがない場合は、このアルゴリズムをお気に入りの言語で記述し、 テストせずにコメントに追加することをお勧めします。 優れたプログラマなら誰でもすぐにこの真に幼稚なアルゴリズムを書くでしょう。 必要なだけ時間をかけてください。 コメントには、言語、費やした時間、およびpastie.orgでの作業へのリンクを示します。
ウィキペディアで、 正しい決定 。
これらすべてが当たり前のように見える人のための小さなホテル。 バイナリ検索とマージソートのほとんどすべての実装にはエラーが含まれます 。 これは、JDKのバイナリ検索を書いた人が言っています。
ネタバレ
よくある間違い：
-0/1/2要素の配列では機能しません
-最初または最後の要素が見つかりません
-配列に要素がない場合、正しく機能しません
-配列内に重複する要素がある場合、正しく機能しません
-配列外の要素へのアクセス
-JDKにあったトランプカード、平均インデックスの計算時の整数のオーバーフロー
PS
この関数は既に標準ライブラリにあると誰かが言うでしょう。
これはそうです、私は同意します。 しかし、これはそのような問題を解決する意味がないという意味ではありません。 すべての単純なタスクが標準ライブラリで既に解決されている場合、そこにはないより複雑なタスクのみがあります。 標準ライブラリの単純な問題でも解決できない場合、これらのより複雑な問題をどのように解決しますか？
方法を説明します。 残念だ。 チームで働いていたときにコード検証を行いました。 多くのプログラマーは、20回試しても最も単純なコードを生成できませんでした！ 彼らは準備ができて座っていることに慣れており、foo（bar（））よりも複雑なものを書くことができず、書くと実装が遅くなり、混乱し、エラーが発生します。
バイナリ検索を作成できるプログラマはわずか10％
All Articles