[音楽再生] 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である。 [音楽再生]