>> [音楽再生]
>> DOUG LLOYD：すべての権利。
だから、バイナリ検索です 我々が使用することができ、アルゴリズム
配列内の要素を検索します。
線形検索とは異なり、それが必要です 特別な条件が事前に満たされ、
場合、それはとてもはるかに効率的です その条件は、実際には、満たされます。
>> だからここの考えは何ですか？
それは分割統治です。
我々は、サイズを小さくします 半分ずつ探索領域
目標数を見つけるためです。
これは、どこにその条件であります しかし、場に出ます。
我々は唯一の力を活用することができます 要素の半分を排除
でも見ずに それらの配列はソートされている場合。
>> それは完全なミックスアップの場合は、 私たちは手からすることはできません
ので、要素の半分を捨てます 我々は廃棄しているのか分かりません。
しかし、配列がソートされている場合、 我々ので、我々は、それを行うことができます
にそのすべてを知っています 私たちは現在の場所の左側
より低くなければなりません 値は、我々現在の位置です。
そして、すべてに 私たちがどこにいるの右側
値よりも大きくなければなりません 我々は、現在見ています。
>> だから擬似コードは何ですか 二分探索のための手順？
私たちは、まで、このプロセスを繰り返します 私たちが通って進むように配列や、
サブアレイの小片 元の配列は、サイズが0です。
中間点を計算します 現在のサブ配列の。
>> あなたが探している値がある場合 配列の要素には、停止します。
あなたはそれを発見しました。
それは素晴らしいことです。
そうでなければ、ターゲットがある場合 途中で何よりも小さく、
我々が探している値は、もしそうであれば ため、私たちが見たものよりも低いです
再びこのプロセスを繰り返しますが、 代わりに、エンドポイントを変更
オリジナルであることの 完全な配列を完了し、
ちょうど左になるように ここでの私達はちょうど見えました。
>> 私たちは、真ん中が高すぎたことを知っていました またはターゲットは、真ん中よりも少なかったです
ので、それならば、存在している必要があります 配列には全く存在しています、
中間点の左側のどこか。
だから、我々は配列を設定します ちょうど左の場所
新しいエンドポイントとしての中点。
逆に、標的である場合 途中で何よりも大きく、
我々は正確に同じことをします プロセスが、その代わりに我々
なるように、開始点を変更します ちょうど中間点の右側に
私達はちょうど計算しました。
そして、我々は再びプロセスを開始します。
>> のがOK、これを視覚化してみましょうか？
だからここに行くと多くは、あります しかし、ここ15要素の配列です。
そして、我々は追跡をすることになるだろう より多くのもの今回の。
だから、線形検索では、我々がありました 単に目標を気に。
しかし、今回は、私たちがしたいです 私たちがどこにあるかを気に
見始めて、どこ 私たちが見て停止しています、
中間点は何ですか 現在の配列の。
そこでここでは、二分探索で行きます。
我々はかなり良い移動するには、正しいですか？
私は下に置くつもりです インデックスのセットここでは以下。
これは、基本的にはどのような要素であります 私たちが話している配列の。
線形検索では、我々 我々としてだけれどもケア、
どのように多くの知っている必要があります 私たちは繰り返し処理している要素、
しかし、我々は実際に何を気にしません 我々は、現在見ている要素。
バイナリ検索では、我々が行います。
そしてそうそれらはちょうどあります そこに少しのガイドとして。
>> だから我々は右、開始することができますか？
まあ、かなりありません。
私が言ったことを覚えておいてください 二分探索は？
私たちは、でそれを行うことはできません 未ソート配列あるいは、
我々はことを保証されていません 特定の要素または値はありません
誤っています 廃棄されたときに我々だけ
配列の半分を無視することにしました。
>> だから、二分探索で1ステップ あなたがソートされた配列を持っている必要があります。
そして、あなたはソートのいずれかを使用することができます 私たちが話したアルゴリズム
その位置にあなたを取得します。
だから今、私たちはどこに位置にいます 我々は、バイナリ検索を実行することができます。
>> それでは、このプロセスを繰り返してみましょう ステップバイステップと維持
私たちが行くように何が起こっているかを追跡。
したがって、最初の私たちは、計算された実行する必要があります 現在の配列の中間点。
まあ、我々は最初の、私たちがしていると言うでしょう すべて、値19を探しています。
私たちは、数19を検索しようとしています。
この最初の要素 配列は、インデックス0に配置されています
これの最後の要素 配列は、インデックス14に位置しています。
そして、私たちはそれらの開始と終了を呼ぶことにします。
>> だから我々はによって中間点を計算 0プラス2で割っ14を追加します。
非常に簡単中間点。
そして、我々はそれを言うことができます 中間点は今7です。
だから15は、我々が探しているものでしょうか？
いいえ、そうではありません。
私たちは19を探しています。
しかし、我々は19の方が大きいことを知っています 私たちは途中で見つけたものより。
>> だから我々は何ができるかであります 開始点を変更します
ただの右側にあることを 中間点、再度処理を繰り返します。
そして、我々はそれを行うとき、私たちは今言います 新たな開始点は、配列の位置8です。
我々は効果的にやったことはあります 15の左側にあるすべてのものを無視しました。
私たちは、半分を排除しました 問題の、そして今、
代わりに検索することの 私たちの配列内の15以上の元素、
我々は7を介して検索する必要があります。
そう8は、新たな開始点です。
14はまだエンドポイントです。
>> そして今、我々は再びこの上を行きます。
私たちは、新しい中間点を計算します。
8プラス14は、2で割った、22で11です。
これは我々が探しているものはありますか？
いいえ、そうではありません。
私たちはの価値を探しています 私達はちょうど見つけたものよりも少ないです。
だから我々は、繰り返しになるだろう プロセスが再び。
我々は、エンドポイントを変更しようとしています ちょうど中間点の左側にあること。
ので、新しいエンドポイントは10となります。
そして今、それは一部だけです アレイは、我々はを通じてソートする必要があります。
だから我々は今排除しました 15の要素12。
私たちは19の場合ことを知っています それは、配列内に存在します
要素の間のどこかに存在している必要があります 数8と要素数10。
>> だから我々は再び新たな中間点を計算します。
8プラス10は、2で割った、18で9です。
この場合には、見て、 目標は中央にあります。
我々は、我々が探している正確に何を発見しました。
私たちは停止することができます。
私たちは正常に完了しました バイナリ検索。
大丈夫。
だから我々は、このアルゴリズムを知っています ターゲットがある場合に動作します
配列の内部のどこか。
このアルゴリズム作業があればい ターゲットは、アレイ内ではないのですか？
さて、それを起動しましょう 再び、このとき、
要素を探してみましょう 視覚的に、私たちが見ることができる16、
配列内のどこにも存在しません。
>> 開始点は再び0となります。
エンドポイントは再び14です。
これらは、最初のインデックスであり、 完全な配列の最後の要素。
そして、私たちはプロセスたちだけを通って行きます 、16を見つけようと、再び通過しました
でも視覚的にかかわらず、我々はすでにすることができます それはそこにあることを行っていないことを言います。
我々は、念のこのアルゴリズムを作りたいです 、実際には、まだいくつかの方法で動作します
ちょうど私たちを残していません 無限ループで立ち往生。
>> だから、最初のステップは何ですか？
中間点を計算します 現在の配列の。
中間点は何ですか 現在のアレイの？
まあ、それは右、7ですか？
2で割った14プラス0は7です。
我々が探しているものを15か？
いいえ。
それはかなり近いですが、私たちは見ています それよりやや大きい値のため。
>> だから我々はそれが起こっていることを知っています 15の左にどこにもありません。
ターゲットはより大きい 中間点でです。
そして、私たちは新たなスタートポイントに設定しました ちょうど真ん中の右側にあること。
中間点はそう、現在7 それでは、新しい開始点が8であるとしましょう​​。
そして、我々は効果的に何をしました 再び行わ無視されます
配列の全体の左半分。
>> 今、私たちは繰り返し 1より多くの時間を処理します。
新しい中間点を計算します。
8プラス14は、2で割った、22で11です。
我々が探しているものを23か？
残念だけど違う。
我々は値を探しています それが23未満です。
ので、この場合には、我々が行っています エンドポイントを変更することだけであることが
現在の中間点の左側にあります。
現在の中間点は11で、 私たちは新しいエンドポイントを設定します
次回のために私達は行きます このプロセスを経て10に。
>> 繰り返しますが、我々は再びプロセスを経ます。
中間点を計算します。
2で割った8 + 10は9です。
我々が探しているものを19か？
残念だけど違う。
我々はまだ探しています それよりも少ない数。
だから我々は、エンドポイントにこの時間を変更します ちょうど中間点の左側になります。
中間点は、現在9 そうエンドポイントは8になります。
そして今、私たちは見ています 単一要素の配列で。
>> この配列の中間点は何ですか？
まあ、それはそれは、8で始まり、 8で終了し、中間点は8です。
それは我々が探しているものはありますか？
我々は17をお探しですか？
いいえ、私たちは16を探しています。
だから、配列内に存在する場合、 それがどこかに存在している必要があります
私たちは現在の場所の左にあります。
だから、私たちは何をするつもりですか？
さて、私たちはなるようにエンドポイントを設定します 現在の中間点の左側にあります。
だから我々は7にエンドポイントを変更します。
あなただけのものを参照しています しかし、ここで起こったのですか？
今ここに調べなさい。
>> スタートは今端部よりも大きいです。
実際には、二つの端部 私たちのアレイを越えて、
スタートポイントは、 今のエンドポイントの後。
まあ、それはしていません 右、何の意味も持た？
だから今、私たちが言うことができることは、私たちです サイズ0のサブアレイを持っています。
そして、一度、私たちはに得ています この時点で、我々はできるようになりました
この要素16を保障 配列には存在しません、
始点理由 およびエンドポイントが交差しています。
そしてそれはありません。
さて、これはわずかであることに気付きます 開始点と終了とは異なります
同じであることを指します。
私たちは、探していた場合 17のために、それは持っているだろう
配列、および開始点であっ その最後の反復のと終点
これらの点は、交差する前に、 我々はそこに17を発見しただろう。
彼らは私達ができることを渡るときだけです 要素がないことを保証
配列内に存在します。
>> それでは、たくさんより少なくてみましょう 線形検索よりも手順。
最悪のシナリオでは、我々は持っていました n個の要素のリストを分割します
繰り返し半分にターゲットを見つけるために、 いずれかのためにターゲット要素
最後のどこかになります 部門、またはそれは全く存在しません。
だから、最悪の場合には、我々がする必要はあり array--を分割知っていますか？
n回のログ。我々 問題をカットする必要があります
時間の半分の一定数インチ
その回数は、ログnです。
>> 最良のシナリオは何ですか？
さて、初めての私たち 中間点を計算し、
我々は、我々が探しているものを見つけます。
以前のすべてで バイナリ検索の例
私達が持っていた場合、私たちはただ、以上の行ってきました 素子15を探して、
私たちは、その直後に発見したことになります。
それは非常に最初にありました。
それはの中点ました スプリットでの最初の試み
二分探索における部門の。
>> だから最悪で 場合は、バイナリ検索が実行されます
実質的に良好であるログnは、内 最悪の場合には、線形探索より。
最良の場合には、バイナリ 検索は、1のオメガで実行されます。
だから、二分探索がたくさんあり​​ます 線形検索よりも良いです、
しかし、あなたはのプロセスに対処する必要があります あなたができる前に最初にあなたの配列をソートします
バイナリ検索のパワーを活用しています。
>> 私はダグロイドです。
これは、CS 50です。