エンジョイC034回目二分探索（2020-11-22）

ほえほえ＠スプシマン @hoehoe1234

エンジョイC 34回目　2020/11/22（日） いよいよエンジョイCコースは修羅の道に入ります。今後は白本、黒本、コメンタリを主軸に講義をします。そういえばC言語の入門書終わってないんですがどうしましょう。。。

ほえほえ＠スプシマン @hoehoe1234

白本、二分探索です。二分探索については有名なアルゴリズムですのでいろいろな書籍に取り上げられていますが、やはり白本は一味違います。精読するに値する書籍と思います（古本は初版は高いので第２版をおすすめします）。 pic.twitter.com/tYxdzqQPlK

拡大

ほえほえ＠スプシマン @hoehoe1234

図上のような昇順にソートされた配列がある場合にユーザ入力のxを探すとします（図左）。この時に見つかればその要素のあるインデックスを、見つからなければたとえば-1を返すとします。

ほえほえ＠スプシマン @hoehoe1234

検索はこれでよいのですが、他の操作を考えてみましょう。この配列の操作には挿入、検索、更新、削除が考えられます。自明ですが検索値して該当要素がない場合に-1を返すような設計をした場合には「検索」にしか使えません。では挿入、更新、削除の位置はどうやって調べれば良いのでしょうか？

ほえほえ＠スプシマン @hoehoe1234

これらの関数を個別に実装することもできますが、４つの関数はほぼ同じようなロジックとなるでしょう。ここでこのような関数を１つにまとめることを考えます。実際にこのあとではB木の各種操作のためにこの関数（２分探索）を発展させた形で使用します。

ほえほえ＠スプシマン @hoehoe1234

返す値iを定義します。 ①0 if x<= k[0] ②n if x > k[n-1] ※nは要素数 ③j if j(1<= j <= n-1)の範囲において、k[j-1] < x <= k[j] このような定義とします。しびれますね素晴らしいです。特に③つめの式に注目です。これは①と②で左右端を処理ずみなのでjの１つ前は必ず定義でき、その定義を利用

ほえほえ＠スプシマン @hoehoe1234

しています。たとえば40を探す場合はjが２となりますがこれは、 k[j-1]->k[1]->34 k[j]->k[2]->50 となり、34 < x(40) <= 50の式を満たします。ですから二分探索ではiとして2を返すことになります。これで式ができました。あとはこの３つの式を利用してコードを書きます。データを定義する手法ですね。

ほえほえ＠スプシマン @hoehoe1234

左(Left）と右(Right)から初めて③の式が成り立つように範囲を縮退していきます。そして範囲が１つになった場合にRが求めるiとなります。まずLeftの設定について考えます。③の式はk[j-1]を見ていました。jの最小値は1です。ですからj-1は0となりこのj-1の代わりにLを設定します。 pic.twitter.com/SAXw3UavCs

拡大

ほえほえ＠スプシマン @hoehoe1234

セットアップ時にはk[L]はk[j-1]を設定します。探す値はk[j-1]より大きいというこですからk[L]には含まれない、すなわちLは求める値ではないということになります。右端はk[j]、すなわち図ではk[n-1]->k[5]となります。これをk[R]と表します。

ほえほえ＠スプシマン @hoehoe1234

初期セットアップ時には k[j-1]にk[L]、L=0 k[j]にK[R]、R=5 を設定します。この範囲に含まれる値は k[0] < x < k[5] -> 23 < x <= 100となります。この時点ではまだ返す値が確定していません。返す値の候補は１～５です。

ほえほえ＠スプシマン @hoehoe1234

ではどうなったら返す値iが確定するのでしょうか？Lから見ていきましょう。K[L]よりxは大きな値です。ある値iを帰す場合にはiの意味はある範囲となります。xの範囲が35～55であればiは2を返します。ですのでxがk[L]よりも大きければをLを左に進めていきます。ではRはどうでしょうか？

ほえほえ＠スプシマン @hoehoe1234

Lとは少し条件が違います。Rはx <= k[R]という条件なのですからk[5]の値100を使うとK[5]->100ですので100以下はどのようなxもマッチしますのでRをずらす条件としてはRの隣（k[R-1]）がx < K[R-1]を満たさなければなりません。

ほえほえ＠スプシマン @hoehoe1234

ここまでの話をまとめると LはK[L]がよりxが大きければ含まれないのでLを右にずらす RはK[R-1]がxより同じか小さければRを左にずらす となります。 ではiが確定するのはいつでしょうか？ そうですね、LとRが隣り合ったときです。 K[L] < x <= K[R]　※LとRは隣り合っている

ほえほえ＠スプシマン @hoehoe1234

LとRが隣り合ったときには、xはK[L]の範囲には含まれなくてK[R]範囲には含まれるということになります。ですからこの場合のRを返せばよいということなります。違う見方をすればもともとの式がK[j-1] < x <= K[j]ですので、J-1がLに、JがRに割り当てていたのですからほしい値はJ、すなわちRとなります。

ほえほえ＠スプシマン @hoehoe1234

コードの解説をしたあとに、実際に感覚として身につけるためにトランプで二分探索をしていただいています。机の上部にソートされた配列を、そして検索値は残りのトランプからシャッフルして選びます。これが二分探索の最終試験です。 pic.twitter.com/EDkxYQUZoj

拡大

ほえほえ＠スプシマン @hoehoe1234

トランプを使って検証します。並べ替える人がチャレンジャー、それ以外の人は横で確認する検査官です。左端の人、なんか見覚えがありますね。 pic.twitter.com/0z1lGvX8uA

拡大

ほえほえ＠スプシマン @hoehoe1234

間違えました。右端の人ですね。最初はうまくいくのですが、縮退の最後になると「あれ？どっちを動かす？」みたいな感じになります。トランプ、いいですね。もちろん全員二分探索卒業試験に合格しました。

ほえほえ＠スプシマン @hoehoe1234

下記忘れていました。LとRはどれぐらい動かせばよいでしょうか？簡単なのは１つづつですね。しかしもっと動かせます。そうです。真ん中をとってLとRの真ん中をMとするとx<=K[M]であればRを、そうでなければLをMの位置にずらせばよいのですね（そのようにすれば依然③の式は成り立つので）。

ほえほえ＠スプシマン @hoehoe1234

がんばれ、ペ●●ンさん。今日は一発卒業試験合格でした！。 pic.twitter.com/CkVcP7V9JK

拡大

ほえほえ＠スプシマン @hoehoe1234

生徒さんのコードレビューにかんしての板書。 要素数は sizeof(arr) / saizeof(arr[0])で求めるんだけど２つ書き方がある。もう一つはsizeof(arr) / sizeof(char)のように要素のサイズに型を使う方。どちらでもいいとは思いますが前者はマクロで書きやすいという利点がありますね。

ほえほえ＠スプシマン @hoehoe1234

通常はそれでよいのですが、文字列の場合はちょっと注意が必要です。図上の"abcd"であれば4文字ですが領域は最後の\0を含めると5文字になりますのでループをする時には実行回数は5回ではなくて4回でなければいけません。つい失念しがちですね。 pic.twitter.com/1AvhueltaO

拡大

ほえほえ＠スプシマン @hoehoe1234

マクロを #define leng(x) (sizeof(x) / sizeof(x[0]))とすると ①for i = 0; i < leng(arr) -1 ではなくて for i = 0; i < leng(arr) - 2 としなければいけませんね。

ほえほえ＠スプシマン @hoehoe1234

黒本再開です。いよいよCS修羅道にはいります。コメンタリをやりたいのですがその前提知識を身につけるための黒本なのですがさらにその解説書籍がほしくなります。今日はforkの説明をしますがforkが行われ前のプロセスの構造を整理します。 pic.twitter.com/yeUZ3o4U4j

拡大

ほえほえ＠スプシマン @hoehoe1234

青で囲んだ部分がセットアップされた状態です。左側はforkを発行する親プロセス（となるプロセス）の仮想メモリ、中央は物理メモリ、右はカーネル（仮想メモリ中）となります。この図で大切なのは、今の親プロセスのPPDA中のu構造体（以下u構造体）がカーネルのC000にマッピングされているというこです

ほえほえ＠スプシマン @hoehoe1234

カーネルはユーザプロセスAを選んで実行するときにプロセスのu構造体を自分のC000からのアドレスにマップします。PPDAに含まれる領域はユーザプロセスからはアクセスできません。アクセスできませんがデータセグメントの上にありプロセスの状況を保有します。