Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [リニアサーチ]
[パトリック·シュミット、ハーバード大学]
[これはCS50です。] [CS50.TV]
検索は、おそらくより頻繁にあなたが思っているよりもやること何かである。
明らかに、毎回あなたは、Webブラウザを開く
Webページ用と検索 -
お気に入りのソーシャルネットワーキングサイト上であなたの友人のための、または検索 -
あなたが捜している。
しかし、それはちょうどあなたが日常的に行うことを検索のほんの一部です。
あなたはクローゼットの中にその1青いシャツを見つけたいときは、
機会のためのその完全な赤いブラウスや、
あなたが検索しています。
あなたが前に行ったことがないことを店に行くときは、
そしてあなたは、農産物売り場でブロッコリーを探している
あなたが検索しています。
あなたは何に気づき始めたかもしれない
あなたが探しているものに依存していること
またはどのように項目が整理され、それらを探しているときに
それはあなたが検索方法に影響を及ぼします。
たとえば、あなたのシャツはクローゼットの中にぶら下がっている場合、
あなたはおそらくはるかに検索しなくても、それを拾うことができます。
あなたがバージンロードを歩くために持っていると仮定している場合
ブロッコリーを取得するには、おそらく他のすべての野菜を見ている
あなたはそのブロッコリーを見つける前に。
またはアルゴリズム - リニアサーチは、そのような検索方法の一例である。
名前が示すように、
このメソッドは、他の後の1は、直線的にするアイテムを検索します。
だから、あなたがお好みの検索エンジンからの結果を見ているとき
そしてあなたは、結果のリストをスクロールして読む
あなたは、線形探索を使用しています。
オーケー。例を見てみましょう。
2、4、0、5、3、7、8、1 - 私たちは番号のリストを持っていると言う -
そして我々は数字の0を探しています。
明らかに、あなただけの0番目の位置にあることがわかります。
しかし、コンピュータ·プログラムは、その幸運はありません。
それは、一度に一つの番号を "見る"ことができる。
だから、リストの先頭から始まる、
それだけで2を "見る"。
その後、プログラムはチェック - 0から2に等しいのですか?
明らかにしない。だから、次の番号は、4に進みます。
4 0に等しくしていますか?いや。
次の1、0。ああ!ゼロは0に等しい。
そこに我々はそれを持っている!これは、3番目の位置にあります。
オーケー。いくつかの擬似コードを見てみましょう。
それだけで長い行のカップルだが、それを一度に1行ずつ見てみましょう。
最初は、関数を定義してみましょう - と我々はそれを線形探索と呼ぶことにしている -
キーと配列 - そしてそれは二つの引数をとります。
鍵は、私たちが探していることをその値である
そう、前の例で、それがゼロであった。
配列は番号のリストです
それは我々が検索しようとしているすべての値を持っています。
だから、私たちがやりたいことは私たちが見たいです -
すべてのポジションからなので、配列の先頭から始まる
配列の一番最後にゴマ - 配列の長さはそう -
一つ一つの位置を見て、それぞれを確認してください。
だから、それはそれは "for"ループが何をしているか。
そして、それぞれの位置で、我々は言うつもり
"我々が探していることをキーに等しいその現在の位置で、その値はありますか?"
だから - 前の例でもう一度、キーは0だった -
ので、我々は "私はゼロに等しい位置にある配列ですか"と言っている
そうである場合、我々はそれが我々が見ている現在の位置だから 'i'を返すようになるだろう。
だから、前の例では、
その3番目の位置だった。
我々は、配列全体を通して行ってきた場合
そして我々は何も見つかっていない -
それでは、私たちは番号500を探していたとしましょう
そのことを明確に例ではありませんでした -
私たちは、何かを返す必要がある
そして我々は-1を返すつもりだ。
それが位置だから、私達はちょうど-1を返している
それは、配列には存在しません。
そして、あなたが関数からそれを取り戻す時を意味するように
それは大丈夫、うーん "と言っています。私は何も見つかりませんでしたと思います。
だから、500があったことがない。 "
線形探索のいいところは、ということです
それは、項目の任意のリストでうまくいく
関係なくアイテムが注文される方法の。
ブロッコリーは農産物の通路のどこにあるかは関係ありません。
あなたは最初から最後まで通路を歩いている限り、
あなたは、それを見つけるにバインドされている
店舗を仮定すると、もちろん、ブロッコリーが不足していない。
しかし、それの最大の強みは、また、それの最大の弱点です。
あなたは200番号のリストを持っていると言う
それは、1〜200の順にソートされます。
あなたは、番号198をお探しの場合は、
あなたは、数字のほぼ全リストを検索する必要が
あなたが探しているものを見つける前に。
より良い方法があるに違いありません!
残りがあるのでご安心ください。
しかし、それは別のビデオのためのトピックです。
また、心配しないでください!
線形探索は、すべての状況で最善の解決策ではないという理由だけで
それは便利になっていないことを意味しません。
そうでなければ、どのように農産物の通路にそのブロッコリーを見つけるか?
私の名前はパトリック·シュミットであり、これはCS50です。
[CS50.TV]