>> [音楽再生]
>> ZAMYLA CHAN：あなたかもしれない最初の事 検索についての通知があることを、我々はすでに
コー​​ドは、私たちのために書かれている。
これは、ディストリビューションのコードと呼ばれています。
だから我々は、単に我々自身を書いていない もう一からコーディングします。
むしろ、我々は、空隙に充填している いくつかの既存のコードで。
>> find.cプログラムは、番号の入力を要求 干し草の山を埋めるために、検索し
針を送信したユーザーのための干し草の山、 それはソートを呼び出すことによってこれを行う
定義された検索、関数 helpers.c中。
そうfind.cはすでに書かれています。
あなたの仕事は、ヘルパーを書くことです。
>> だから我々は何をしているの？
我々は2つ​​の機能を実装している。
値trueを返し、検索、 帰国、干し草の山で発見されている
偽の値である場合 いない干し草の山の中。
そして、我々はまた、ソートを実装している その値と呼ばれる配列をソートします。
>> それでは、検索に取り組むみましょう。
サーチは、現在のように実現される 線形探索が、あなたは多くを行うことができます
それよりも優れています。
線形探索は、Oに実装されています N個の時間が、これは非常に遅い。
が、それは検索することができます それに与えられた任意のリスト。
あなたの仕事は、バイナリサーチを実装することです、 ログnの時のOを実行している。
これはかなり速いです。
>> しかし、規定があります。
バイナリサーチは、検索することができます 事前にソートされたリストをスクロール。
これはなぜですか？
>> さて例を見てみましょう。
値の配列を指定して、干し草の山、 我々は見ているつもりです
針のため。
この例では、 整数3。
バイナリ検索が動作する方法はある 我々は中間の値を比較
多くの針状に配列、どのように 我々は、中に電話帳を開いた
週ゼロページ。
>> そうするための中間値を比較した後 針は、次のいずれか破棄することができます
左または配列の右半分 あなたの境界を締めて。
我々の針三ので、この場合は、 10未満である、中間値、
右バウンドが低下する可能性があります。
しかし、あなたの境界を作ってみる できるだけタイト。
中間値は、針でない場合には、 あなたはあなたがする必要がないことを知っている
検索に含める。
だから、右のバインドされている締めができます ほんの少し検索限度、
などなどまで、 あなたの針を見つける。
>> それでは、擬似コードは次のようにしますか？
まあ我々はまだを通して見ている間 リストと、まだに要素を持っている
中を見て、我​​々は、リストの中間を取る とに、その中間値を比較
私たちの針。
それらが等しいならば、それは我々がしたことを意味 針を発見し、我々はできる
trueを返します。
>> そうでなければ、針は未満である場合 中間値、そしてそれは我々を意味します
ちょうど半​​分を破棄し、することができます 配列の左側を検索する。
そうでなければ、我々は、検索します 配列の右側。
そして、最後には、いずれかを持っていない場合 以上の要素を検索するために残されますが
その後、まだ針を発見していない falseを返すので、針
間違いなく干し草の山ではありません。
>> この擬似コードについて、今きちんとしたもの バイナリサーチではそれができるということです
反復のどちらとして解釈 または再帰実装。
あなたが呼ばれるのであれば、それは再帰的になる 検索中の検索機能
配列のどちらか半分に機能します。
我々は少し後における再帰をカバーします もちろん、それがあることを知っていますか
オプションあなたが試してみたい場合。
>> 今度は、ソートを見てみましょう。
並べ替え列と整数を取り 配列のサイズであるN、。
現在、様々な異なったタイプがあります ある種の、あなたは、いくつかを見ることができます
デモや説明はショートパンツ。
私たちの戻り値の型 ソート機能は無効となります。
だから我々はつもりはないことを意味します ソートから任意の配列を返します。
私たちは、実際には非常に変更しようとしている 私たちに渡された配列。
>> 配列であるため、それが可能だ 我々は今では、参照により渡されます
この後の詳細が、参照してください。 通過の間に本質的な違い
整数やパッシングのようなものでの 配列に、あるときに
整数を渡し、Cはちょうどしようとしている その整数のコピーを作成し、合格
それ関数である。
元の変数は変更されません 関数が一旦終了する。
アレイと、他方では、それがだ コピーを作成します。また、あなたがよいない
実際に編集することが 非常に配列そのもの。
>> だから、ソートの一種である 選択ソート。
選択ソートは、から始まることによって動作します それから始まり、そしてあなたが繰り返し処理
何度最小の要素を見つける。
そして、あなたはその最小を交換 最初の1を持つ要素。
そして、あなたは番目の要素に移動 、次に小さいを見つける
その要素とは、スワップすることで 配列の2番目の要素のため
最初の要素はすでにソートされます。
だから、あなたは、すべての継続 最小を特定の要素
価値と、それをスワップアウト。
>> 私は0に等しいため、非常に最初の要素 Nマイナス1には、次のように比較するつもりだ
その後、すべての次の値と見つける 最小値のインデックス。
あなたが最小値インデックスが見つかったら、 あなたは、配列の値を入れ替えることができます
最小値と配列I.
>> 並べ替え、別のタイプのあなたができること 実装バブルソートです。
リストの上ので、バブルソートを反復 隣接する要素を比較し、
その要素を交換 間違った順序である。
そして、このように、最大​​の要素 バブルは終わりにします。
そしてリストは一回もう替えられていない 要素が入れ替わっている。
>> ので、これらの種類の2つの例である あなたが実装できるアルゴリズム
検索プログラム。
あなたは、ソート完了し、あなたがしたら 検索を行って、あなたは完了です。
私の名前はZamylaであり、これはCS50である。
>> [音楽再生]