>> ZAMYLA CHAN：あなたかもしれない最初の事 検索についての通知があることを、我々はすでに
コー​​ドは、私たちのために書かれている。
これは、ディストリビューションのコードと呼ばれています。
だから我々は、単に我々自身を書いていない もう一からコーディングします。
むしろ、我々は、空隙に充填している いくつかの既存のコードで。
>> find.cプログラムは、番号の入力を要求 干し草の山を埋めるために、検索し
針を送信したユーザーのための干し草の山、 それはソートを呼び出すことによってこれを行う
定義された検索、関数 helpers.c中。
そうfind.cはすでに書かれています。
あなたの仕事は、ヘルパーを書くことです。
>> だから我々は何をしているの？
我々は2つ​​の機能を実装している。
値trueを返し、検索、 帰国、干し草の山で発見されている
偽の値である場合 いない干し草の山の中。
そして、我々はまた、ソートを実装している、 その値と呼ばれる配列をソートします。
それでは、検索に取り組むみましょう。
>> 検索は、現在実装されている 線形探索など。
しかし、あなたはそれよりもはるかに良いを行うことができます。
線形探索は、NのOに実装されています かなり遅い時間、それものの
それに与えられた任意のリストを検索することができます。
あなたの仕事は、バイナリサーチを実装することです、 ログnの時のOを実行している。
これはかなり速いです。
>> しかし、規定があります。
バイナリサーチは、検索することができます 事前にソートされたリストをスクロール。
これはなぜですか？
さて、例を見てみましょう。
値の配列を指定して、干し草の山、 我々は見ているつもりです
針のため、この中 たとえば、整数3。
>> バイナリ検索が動作する方法はある 我々は中間の値を比較
多くの針状に配列、どのように 我々は、中に電話帳を開いた
週0ページ。
そうするための中間値を比較した後 針は、次のいずれか破棄することができます
左または配列の右半分 あなたの境界を締めて。
この場合、3は、我々の針であり、 10未満、中間値、
右バウンドが低下する可能性があります。
>> しかし、あなたの境界を作ってみる できるだけタイト。
中間値は、針でない場合には、 あなたはあなたがする必要がないことを知っている
検索に含める。
だから、バインドユーザの権利が締めることができます ほんの少し検索限度、
などなど、時まで あなたの針を見つける。
>> それでは、擬似を行います コー​​ドは次のように？
さて、我々はまだを通して見ている間 リストと、まだ持っている
中を見ての要素が、我々​​は真ん中を取る リストとそれを比較する
私たちの針への中間値。
それらが等しいならば、それは我々がしたことを意味 針を見つけ、我々はできる
trueを返します。
>> そうでなければ、針は未満である場合 中間値、そしてそれは我々を意味します
ちょうど半​​分を破棄することができ 配列の左側を検索する。
そうでなければ、我々は、検索します 配列の右側。
そして、最後には、いずれかを持っていない場合 以上の要素を検索するために残されますが
まだあなたの針を見つけていない、 あなたはfalseを返します。
間違いなく針理由 干し草の山ではありません。
>> さて、この疑似約1きちんとした事 バイナリサーチのコードは、それができることです
反復いずれかとして解釈される または再帰実装。
あなたが呼ばれるのであれば、それは再帰的になる 検索中の検索機能
配列のどちらか半分に機能します。
私たちは、再帰を少し取り上げます 後でコース。
しかし、それがオプションであることを知っていますか あなたは試してみたい場合。