リニア検索とバイナリ検索の違いは何ですか？

Question

リニア検索とバイナリ検索の違いは何ですか？

Answer 1

linear searchは、ジャンプすることなく一度に1つの項目をルック・ダウンします。複雑さの点では、これはO(n)検索です。リストを検索するのにかかる時間は、リストと同じ割合で大きくなります。

binary searchは、ソートされたリストの途中から開始し、探している値よりも大きいか小さいかを確認します。これは、値がリストの最初または後ろにあるかどうかを判断します。サブリストの途中にジャンプして、再度比較するなどです。これは、人間が辞書の中の単語をどのように見ているのか（私たちはより良いヒューリスティックを使用しますが、明らかに - あなたが "cat" "M"で始める）。複雑な意味では、これはO(log n)の検索です。検索操作の数は、各操作で「検索スペース」を半分にしているため、リストよりも遅くなります。

例として、文字のA-Zリスト（インデックス0-25、インデックス20の値を探しています）でUを探しているとします。

線形検索が求めるだろう：

list[0] == 'U'？ No.
list[1] == 'U'？ No.
list[2] == 'U'？ No.
list[3] == 'U'？ No.
list[4] == 'U'？ No.
list[5] == 'U'？ No.
... list[20] == 'U'？はい。完成しました。

バイナリ検索を求めるだろう：

は 'U' で（ 'M'）list[12]の比較：小規模、さらに上に見えます。 （範囲= 13-25）
list[19]（ 'T'）と 'U'を比較してください。 （範囲= 20-25）
list[22]（ 'W'）と 'U'を比較：より早く見てください。 （範囲= 20-21）
list[20]（ 'U'）と 'U'を比較してください：見つかりました！完成しました。
2を比較

：

• バイナリ検索をソートする入力データを必要とします。線形探索は行わない
• バイナリ検索では、を注文する必要があります。比較;リニア検索は等価比較のみを必要とする。
• バイナリ検索では複雑さがO（log n）である。線形探索は前述のように複雑さO（n）を有する。
• 二分探索はデータへのランダムアクセスを必要とする。線形検索が唯一のシーケンシャルアクセスが必要です（これは非常に重要なことができます - それは意味線形検索することができますストリーム任意のサイズのデータ）電話帳にあなたの方法を見つけることの二つの異なる方法として、それの

Answer 2

と思います。あなたが探しているものが見つかるまで、すべての名前を読んで最初から線形検索が始まります。一方、バイナリ検索は、ブックを開いて（通常は中央に）、ページの上にある名前を見て、探している名前があなたのものよりも大きいか小さいかを判断します探しています。あなたが探している名前が大きい場合、あなたはこの非常にファッションの本の上部を検索し続けます。

Answer 3

リニア検索は、値のリストの始めから開始し、検索する結果の順番で1をチェックします。

ソートされた配列の途中でバイナリ検索が開始され、探している値がどちらの側にあるかが判断されます。その後、アレイの「半分」は同じ方法で再び検索され、毎回2回ずつ結果が分割されます。

Answer 4

私は、リニア検索値をソートする必要がないため

1 difference-追加したいと思います。

ただし、バイナリ検索の場合、値はソート順である必要があります。

Answer 5

逐次検索とも呼ばれる線形検索は、最初から順番に各要素を調べて、目的の要素がデータ構造内に存在するかどうかを調べます。データの量が少ない場合、この検索は高速です。簡単ですが、検索するデータの量に比例して必要な作業があります。要素の数を2倍にすると、必要な要素がない場合は検索時間が2倍になります。

バイナリ検索は、より大きな配列に対して効率的です。これで我々は中間の要素をチェックします。値が大きい場合は前半を、それ以外の場合は後半を見てください。目的の項目が見つかるまでこれを繰り返します。バイナリ検索のためにテーブルをソートする必要があります。各反復でデータの半分を削除します。対数です。

検索する要素が1000個ある場合、バイナリ検索には約10ステップ、直線検索では1000ステップが必要です。迅速バイナリサーチの勝利は、コストに見合う価値があるかどうかについて審議することを確認し、線形探索はOで実行される（N）回のため、バイナリ検索がより良いパフォーマンス

Answer 6

バイナリ検索はO（LOGN）の時間で実行されますリストをソートしたままにする（バイナリ検索を使用できるようにする）。私。多くの挿入/削除操作と時折の検索のみがある場合、バイナリ検索は線形検索よりも全体的に遅くなる可能性があります。

Answer 7

を持っているのに対し、

Answer 8

試してみてください：ランダムな名前「姓、名」を選んで電話帳で探します。

1回目：書籍の冒頭で始め、見つかるまで名前を読むか、それがアルファベット順に出現する場所を見つけてそこにはないことに気づく。

2回目：半角で本を開き、ページを見ます。この人物が左か右にいるべきか自問してください。それがどちらのものであれ、それを1/2にして、その真ん中を見つけてください。エントリが存在するページを見つけて、同じプロセスを列に適用するか、以前のようにページ上の名前に沿って直線的に検索するまで、この手順を繰り返します。

時間を両方の方法で報告してください！

[あなたが持っているすべての名前のリストは、ソートされていない場合にも優れている何のアプローチを検討...]

Answer 9

線形探索はジャンプせずにリスト、一度に一つの項目を、下に見えます。複雑さの点でこれはO（n）検索です。リストを検索するのにかかる時間は、リストと同じ割合で大きくなります。

バイナリ検索は、ソートされたリストの途中から開始し、探している値よりも大きいか小さいかを確認します。リスト。サブリストの途中にジャンプして、再度比較するなどです。これは、人間が辞書の中の単語をどのように見ているのか（私たちはより良いヒューリスティックを使用しますが、明らかに - あなたが "cat" "M"で始める）。複雑さの点でこれはO（log n）検索です。検索操作の数は、各操作で「検索スペース」を半分にするため、リストよりも遅くなります。

Answer 10

リニア検索は、データのリスト内の各要素を調べて、ターゲットを見つけたり、最後に到達するまで機能します。これにより、指定されたリストでO（n）のパフォーマンスが得られます。 バイナリ検索には、データをソートする必要があります。この情報を活用して、目標を見つけるために見なければならない項目の数を減らすことができます。データの中のランダムなアイテム（中間のアイテムと呼ぶ）を見て、そのアイテムがターゲットよりも大きい場合、そのアイテムの右側にあるすべてのアイテムもターゲットよりも大きくなることがわかります。これは、データの左部分だけを見る必要があることを意味します。基本的には、ターゲットを探してミスするたびに、残りのアイテムの半分を削除することができます。これは私たちに良いO（log n）時間の複雑さを与えます。

ソートデータは、最も効率的なアルゴリズムであっても、線形検索（最速のソートアルゴリズムはO（n * log n））よりも遅くなることを覚えておいてください。したがって、後で単一のバイナリ検索を実行するためだけにデータを並べ替えるべきではありません。しかし、多くの検索を実行する場合（少なくともO（log n）の検索など）、バイナリ検索を実行できるようにデータを並べ替えることは価値があります。このような状況では、ハッシュテーブルなどの他のデータ構造も考慮する必要があります。

Answer 11

Linear Searchは、検索された値が見つかるまで項目を検索します。

効率：O(n)

例のPythonコード：

test_list = [1, 3, 9, 11, 15, 19, 29] 
test_val1 = 25 
test_val2 = 15 

def linear_search(input_array, search_value): 
    index = 0 
    while (index < len(input_array)) and (input_array[index] < search_value): 
     index += 1 
    if index >= len(input_array) or input_array[index] != search_value: 
     return -1 

    return index 


print linear_search(test_list, test_val1) 
print linear_search(test_list, test_val2) 

Binary Searchは、配列の中央要素を見出します。中間値が検索値よりも大きいか小さいかをチェックします。小さい場合は、配列の左側を取得し、その部分の中央の要素を見つけます。大きい場合は、配列の右部分を取得します。検索された値が見つかるまで操作をループします。配列に値がない場合は、検索が終了します。

効率：O(logn)

例のPythonコード：

test_list = [1, 3, 9, 11, 15, 19, 29] 
test_val1 = 25 
test_val2 = 15 

def binary_search(input_array, value): 
    low = 0 
    high = len(input_array) - 1 
    while low <= high: 
     mid = (low + high)/2 
     if input_array[mid] == value: 
      return mid 
     elif input_array[mid] < value: 
      low = mid + 1 
     else: 
      high = mid - 1 

    return -1 


print binary_search(test_list, test_val1) 
print binary_search(test_list, test_val2) 

また、あなたがここにリニアおよびバイナリ検索についての可視化情報を見ることができます：https://www.cs.usfca.edu/~galles/visualization/Search.html