>> ROBボーデンは：こんにちは、私はロブだ。
どのように我々は二分探索を採用するのですか？
では、見ていきましょう。
だから、この検索は、我々が行っていることに注意してください 再帰的に実装します。
また、バイナリ検索を実装することができます 反復して、あなたがそれをしたのであれば、
それはまったく問題ありません。
>> 今最初に、覚えてみましょう 検索のパラメータがあることを意味する。
ここでは、あるint型の値を参照してください ユーザが値であると考え
を検索する。
私たちは、これはint値の配列を参照してください。 我々はしているている配列です
値を検索する。
そして、我々はあるint型のnを参照してください。 私たちの配列の長さ。
>> さて、最初にまず。
我々は、nが0に等しいかどうかを確認し、中 その場合、我々はfalseを返します。
それはちょうど私たちが空を持っている場合言っている 配列の値は、明らかではありません
空の配列なので、我々はfalseを返すことができます。
>> 今、私たちは実際にバイナリをやってみたい バイナリサーチの検索部。
そこで、我々は真ん中を見つけたい この配列の要素。
ここでは、中央の分割Nに等しいと言う 中間要素であるので2によって
の長さになるだろう 私たちのアレイは、2で割った。
今、私たちはいるかどうかを確認するつもりだ 中央の要素は、私たちがしている値と同じ
を検索する。
値の中間の値に等しいそうであれば、我々は 我々が見つけたので、trueを返すことができます
私たちの配列の値。
>> しかし、それが本当ではなかった場合には、今 我々は、再帰を行う必要があります
二分探索のステップ。
我々はどちらかに検索する必要があります 配列の左またはへ
配列の真ん中。
だからここでは、中央の値である場合に言う 値未満、即ち、その値を意味する
真ん中よりも大きかった 配列の。
だから、値が右側にある必要があります 我々だけを見て要素。
>> だからここに、我々はするつもりだ 再帰的に検索します。
そして、我々は我々が通っているのか見てみましょう 第二はこれに。
しかし、我々はに検索するつもりだ 中央の要素の右側。
および他の場合には、そのつまり 値は、真ん中より少なかった
アレイと、私たちはなるだろう 左側の検索します。
今、左があることを行っている を見て少し簡単。
そこで、我々は我々が再帰的にしていることがわかり どこで最初の検索を呼び出す
引数には、再び、値であり、 私たちは、以上見ている。
第二引数はなるだろう 我々は以上の探していた配列。
最後の要素は現在の中間である。
最後のパラメータが私たちのint型であることを覚えている N、それは我々の配列の長さですので。
>> 検索する再帰呼び出しでは、我々はしている 今では、長さを言って
配列は中です。
だから、私たちのアレイは、サイズ20、我々であった場合は、 中間であるため、インデックス10に検索
20は、2で割った、それは我々がしていることを意味 新規として10を渡す
私たちの配列の長さ。
覚えているあなたは、配列を持っているとき 長さ10の、それが有効なことを意味する
要素は、0から9までのインデックスである。
だから、これは私たちがしたい正確に何である 左 - 私たちの更新された配列を指定する
真ん中の要素から配列。
>> だから、右に見てすることです。 少し難しい。
今最初に、長さを考えてみましょう の右側の配列の
真ん中の要素。
だから、私たちのアレイはサイズnのだったならば、 新しい配列のサイズは、Nマイナスになります
真ん中のマイナス1。
それでは、n個のマイナス真ん中を考えてみましょう。
>> 繰り返しますが、配列のサイズが20であった場合 私たちは、真ん中を取得するために2で割る、
その真ん中には、その後、10 nはマイナスミドル 私たちの10ので、10を与えるために起こっている
真ん中の右側にある要素。
しかし、我々はまた、このマイナスを持っている 1、我々はしたくないので、
ミドル自体は含まれています。
だから、Nマイナス真ん中マイナス1は、私たちができます 右の要素の総数
配列内の中央のインデックス。
>> 今ここに、その中を覚えている パラメータは、値配列です。
だからここに、我々は渡している 更新された値の配列。
この値がプラスミドルプラス1です 実際に再帰的に呼び出して言って
検索、新しい配列を渡し、どこに その新しい配列が途中で開始します
プラス私たちの元の値配列の1。
>> 今ではそのための代替構文、 あなたは、ポインタを参照することです開始しました
アンパサンド値真ん中に1を加えた。
そう、真ん中のアドレスをつかむ 値のプラス1の要素。
>> 今、あなたが快適ではなかった場合は、 あなたは、そのような配列を変更する
また、使用し、これを実装している可能性が 再帰的なヘルパー関数、どこ
そのヘルパー関数を取る 以上の引数。
だからではなく、値だけを取る、 配列、および配列のサイズ、
ヘルパー関数は、より多くを取ることができる 低い屈折率を含めた引数、
あなたは配列に約気になること あなたが気にアッパーインデックス
アレイに関する。
>> だから、両方の下を追跡する インデックスとアッパーインデックス、あなたはしないでください
これまでに変更する必要があります 元の値の配列。
あなただけを続けることができます 値の配列を使用します。
しかし、ここで、我々はヘルパーを必要としない気づく 限り、我々はしているとしても機能
オリジナルを変更することをいとわ values​​配列。
私たちは、渡すために喜んでいる 更新された値。
>> 今、私たちは以上のバイナリ検索することはできません 未ソートされた配列。
それでは、これは整理得ることができます -
今、その種が過去である気づく2 パラメータがある値を、int型
我々は、ソートしているアレイと、int型のN、 配列の長さであること
私たちは、ソートしています。
だから、ここでは、実装したい ソートアルゴリズム
それは、nのoを二乗である。
あなたは、バブルソート、選択を選ぶことができる 並べ替え、または挿入ソート、または
我々は持っていないいくつかの他の並べ替え クラスに見られる。
しかし、ここで、我々はするつもりだ 選択ソートを使用しています。
>> そこで、我々は繰り返し処理をするつもりだ 配列全体にわたる。
さて、ここで我々は繰り返し処理していることがわかります 0からnまでのマイナス1。
なぜわざわざNまで？
まあ、我々はすでにソートした場合は、最初の その後、Nマイナス1の要素、
すでになければなりませんどのような非常に最後の要素 正しい場所に、その上の仕分け
配列全体。
>> 今、どのように選択を覚えている ソート機能します。
私たちは、全アレイ上に行くつもりだ 内の最小値を探して
アレイおよびスティックその 先頭に。
その後、我々は全体の上に行くつもりだ 配列には、再び第2探し
最小要素、スティック、その の2番目の位置にある
配列など。
だから、それはこれが何をしているかだ。
>> ここで、我々は我々がしていることを見ている 現在の最小設定
i番目のインデックスに値。
だから、最初の反復では、我々は行っている 最小値はことを考慮すべき
私たちの配列の先頭。
その後、我々は反復するために行っている をチェック、アレイの残りの部分、
そこにいる場合よりも小さい任意の要素を参照してください。 我々は現在の通貨1
最小値を考慮。
>> だからここに、Jプラス1値 - それはです 我々は現在よりも少ない
最小値を考慮。
その後、我々は何を更新するつもりだ 我々は最小だと思う
インデックスjに1を加えた。
だから、アレイ全体そのために、 この後のループでは、最小
から最小の要素であるべき アレイ内のi番目の位置。
>> 我々はそれを持っていたら、交換することができます i番目の位置に最小値
配列内の。
だから、これは標準的なスワップです。
我々は一時的な値に格納 - アレイ内のi番目の値 -
アレイ内のi番目の値に入れ そこに属している最小値、
して、どこに店に戻っ なるように使用される現在の最小値
アレイ内のi番目の値なので、 我々はそれを失うことはありませんでしたことを。
>> だから、それはに続く 次の繰り返し。
我々は、第二​​を探し始めます 最小値とにそれを挿入する
第二の位置。
第三の反復で、私達はのために見ていきます 第三の最小値およびインサート
その第三の位置に、など 私たちはソートされた配列を持つまでに。
私の名前はロブであり、この 選択ソートた。