2

JonBentleyのProgrammingPearls、2ndEditionのセクション9.3を読んでいます。

94ページで、Jonは、nが1000であるという事実を利用して、改良された二分探索アルゴリズムの実装を示しました(ターゲットを見つけるために1000個の数値を検索します)。

プログラムの最後には、次のようになります。

if p > 1000 || x[p] != t
    p = -1

私の質問は、pが正確に1000の場合はどうなるかということです。pが1000の場合、次のようにエラーになるはずです。

if p >= 1000 || x[p] != t
    p = -1

とにかく、コードのこの部分は、93ページのコードから翻訳されています。

if p >= n || x[p] != t
    p = -1

私の理解は正しいですか?これがタイプミスなのか、それともpが1000の場合を条件に含める必要がないのか疑問に思っています。

もう1つの質問は、94ページの5〜6行目に、次のように書かれています。最初のテストが失敗し、lがゼロのままの場合、プログラムはpのビットを順番に計算します。最上位ビットが最初になります。

ここではどういう意味ですか?そして、最初のテストが失敗したとき、lは0ではなく-1にすべきではありませんか?

誰でもこの声明について詳しく説明できますか?

PSジョンのメールアドレスが見つかりません。それ以外の場合は、これらの質問に答えます。:-(

4

1 に答える 1

3

タイプミスです。lの最大値は999(1000-512 + 256 + .. + 1、)であるため、p = l + 1の最大値は1000です。ハードコードされたバージョンのbinsearch(リスト9.8)では明らかです。

そして、ここ(Alg.4)で実際のCコード(擬似コードではない)をif(p> = n ||

于 2012-05-18T12:03:48.183 に答える