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