T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS バイナリーサーチなど(1)

<<   作成日時 : 2016/01/12 00:02   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

コンピュータサイエンスとプログラミング入門(Part2)が始まっているのですが、講義を聴いてもなかなか頭に入ってきません。どうも(Part1)の最後の部分をやっていないのが理由のようです。なので遅まきながら復習です。

(Part1)の最後は、ソートされているリストのなかの1つのデータを検索する問題で、基本的にはバイナリーサーチの検討になります。
まず、頭から順繰りに検索する関数です。
画像

これは、\(s\) に(予めソートされている)リスト、\(e\) に検索するデータを引数にするものです。
論理を見ていくと、 \(s\) の長さを最大として、ひとつひとつ 0 からインクリメントして調べていって、一致した場合、\(True\) と 、\(e\) のあった場所 \(numCompares\) を出力します。ここで、\(e\) が \(s\) の最低値より下回れば\(True\) の代わりに \(False\) が出力されることになります。
このプログラムの複雑はリストの長さに対して線形となります。本当は \(e\) に入れるデータによって、実行時間は違ってしまいます。しかし、こういうときは最大値を考えるのでリストの長さに比例するということですね。

次が今回の主題である「バイナリーサーチ」となります。
画像

これは行き当たりばったりで作ったのか?ちょっと分かり難いですね。まず、\(search1\) という関数を呼んで、\(s\) の \(長さ-1\) を計算して、本当のバイナリーサーチである \(bsearch\) という関数を呼ぶ形になってますが、ここに \(print\) を付けて戻り値 \((True/False)\) を出力するようになっていますね。
では、\(search1\) を見ていきましょう。
\(s\) の長さが2になってしまったら、どちらかが \(e\) と同値かどうか? \(s[first]==e or s[last]==e\) という論理で戻り値 \((True/False)\) を確定します。
\(s\) の長さが2にならないうちは、\(mid=first+(last-first)/2\) というようにいわゆる真ん中を見付けて、そこのデータと \(e\) を比較して同じなら、戻り値 \(True\) を確定して終わります。
違うなら、大小を見て右半分か、左半分の範囲を設定して再帰処理になるということになります。

これを確認するプログラムは次に示すものです。
画像

まず、上2つの結果です。下に範囲外の場合です。
画像

次の2つの結果です。上に範囲外の場合です。
画像

次の2つ結果は、順繰りサーチで、範囲内にデータがある場合と、上に範囲外の場合です。
画像

最後の2つは上の条件をバイナリーサーチで行ったものです。
画像

手数を考えたとき、リストの長さを \(n\) として、これを半分にすることを実施していく訳ですが、\(n= 2^{a}\; \rightarrow\; a= \log_{2}n\) ということで対数モデル \(O(\log_{2}n)\) ということになります。

今日はこの辺で。。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
バイナリーサーチなど(1) T_NAKAの阿房ブログ/BIGLOBEウェブリブログ
文字サイズ:       閉じる