ZAMYLA CHAN：あなたかもしれない最初の事 検索についての通知があることを、我々はすでに コー​​ドは、私たちのために書かれている。 これは、ディストリビューションのコードと呼ばれています。 だから我々は、単に我々自身を書いていない もう一からコーディングします。 むしろ、我々は、空隙に充填している いくつかの既存のコードで。 

find.cプログラムは、番号の入力を要求 干し草の山を埋めるために、検索し 針を送信したユーザーのための干し草の山、 それはソートを呼び出すことによってこれを行う 定義された検索、関数 helpers.c中。 そうfind.cはすでに書かれています。 あなたの仕事は、ヘルパーを書くことです。 

だから我々は何をしているの？ 我々は2つ​​の機能を実装している。 値trueを返し、検索、 帰国、干し草の山で発見されている 偽の値である場合 いない干し草の山の中。 そして、我々はまた、ソートを実装している、 その値と呼ばれる配列をソートします。 それでは、検索に取り組むみましょう。 

検索は、現在実装されている 線形探索など。 しかし、あなたはそれよりもはるかに良いを行うことができます。 線形探索は、NのOに実装されています かなり遅い時間、それものの それに与えられた任意のリストを検索することができます。 あなたの仕事は、バイナリサーチを実装することです、 ログnの時のOを実行している。 これはかなり速いです。 

しかし、規定があります。 バイナリサーチは、検索することができます 事前にソートされたリストをスクロール。 これはなぜですか？ さて、例を見てみましょう。 値の配列を指定して、干し草の山、 我々は見ているつもりです 針のため、この中 たとえば、整数3。 

バイナリ検索が動作する方法はある 我々は中間の値を比較 多くの針状に配列、どのように 我々は、中に電話帳を開いた 週0ページ。 そうするための中間値を比較した後 針は、次のいずれか破棄することができます 左または配列の右半分 あなたの境界を締めて。 この場合、3は、我々の針であり、 10未満、中間値、 右バウンドが低下する可能性があります。 

しかし、あなたの境界を作ってみる できるだけタイト。 中間値は、針でない場合には、 あなたはあなたがする必要がないことを知っている 検索に含める。 だから、バインドユーザの権利が締めることができます ほんの少し検索限度、 などなど、時まで あなたの針を見つける。 

それでは、擬似を行います コー​​ドは次のように？ さて、我々はまだを通して見ている間 リストと、まだ持っている 中を見ての要素が、我々​​は真ん中を取る リストとそれを比較する 私たちの針への中間値。 それらが等しいならば、それは我々がしたことを意味 針を見つけ、我々はできる trueを返します。 

そうでなければ、針は未満である場合 中間値、そしてそれは我々を意味します ちょうど半​​分を破棄することができ 配列の左側を検索する。 そうでなければ、我々は、検索します 配列の右側。 そして、最後には、いずれかを持っていない場合 以上の要素を検索するために残されますが まだあなたの針を見つけていない、 あなたはfalseを返します。 間違いなく針理由 干し草の山ではありません。 

さて、この疑似約1きちんとした事 バイナリサーチのコードは、それができることです 反復いずれかとして解釈される または再帰実装。 あなたが呼ばれるのであれば、それは再帰的になる 検索中の検索機能 配列のどちらか半分に機能します。 私たちは、再帰を少し取り上げます 後でコース。 しかし、それがオプションであることを知っていますか あなたは試してみたい場合。