51

線形検索と二分検索の違いは何ですか？

4

11 に答える 11

126

線形検索では、ジャンプせずに、一度に1つのアイテムずつリストを検索します。複雑な用語では、これはO(n)検索です。リストの検索にかかる時間は、リストと同じ速度で長くなります。

二分探索とは、ソートされたリストの中央から開始し、それが探している値よりも大きいか小さいかを確認することです。これにより、値がリストの前半か後半かが決まります。サブリストの途中までジャンプして、もう一度比較します。これは、人間が通常辞書で単語を検索する方法とほぼ同じです（ただし、より優れたヒューリスティックを使用していることは明らかです。「猫」を探している場合は、そうではありません。 「M」から始めます）。複雑な用語では、これはO(log n)検索です。各操作で「検索スペース」が半分になるため、検索操作の数はリストよりもゆっくりと増加します。

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

線形検索は次のように尋ねます。

list[0] == 'U'？いいえ
list[1] == 'U'？いいえ
list[2] == 'U'？いいえ
list[3] == 'U'？いいえ
list[4] == 'U'？いいえ
list[5] == 'U'？いいえ
... list[20] == 'U'？はい。終了した。

二分探索は尋ねるでしょう：

list[12]（'M'）と'U'を比較してください：小さい、さらに見てください。（範囲= 13-25）（'T'）と'U'を
比較してください：小さい、さらに見てください。list[19]（範囲= 20-25）（'W'）と'U'を
比較してください：大きく、先を見てください。list[22]（範囲= 20-21）（'U'）と'U'を
比較してください：見つかりました！list[20]終了した。

2つの比較：

  • 二分探索では、入力データを並べ替える必要があります。線形探索はしません
  • 二分探索には順序比較が必要です。線形探索は等式比較のみを必要とします
  • 二分探索の複雑さはO（log n）;です。前に説明したように、線形探索の複雑さはO（n）です。
  • 二分探索では、データへのランダムアクセスが必要です。線形検索はシーケンシャルアクセスのみを必要とします（これは非常に重要な場合があります-線形検索は任意のサイズのデータ​​をストリーミングできることを意味します）
于 2009-03-31T06:25:17.543 に答える
71

電話帳で自分の道を見つける2つの異なる方法と考えてください。線形検索は最初から始まり、探しているものが見つかるまですべての名前を読み取ります。一方、バイナリ検索では、本を開いて（通常は中央で）、ページの上部にある名前を見て、探している名前が自分の名前よりも大きいか小さいかを判断します。探しています。探している名前が大きい場合は、この方法で本の上部を検索し続けます。

于 2009-03-31T06:25:24.983 に答える
16

線形検索は、ターゲットが見つかるか最後に到達するまで、データのリスト内の各要素を調べることによって機能します。これにより、特定のリストで O(n) のパフォーマンスが得られます。二分探索には、データをソートする必要があるという前提条件があります。この情報を活用して、ターゲットを見つけるために調べる必要があるアイテムの数を減らすことができます。データ内のランダムなアイテム (真ん中のアイテムとしましょう) を見て、そのアイテムが目標よりも大きい場合、そのアイテムの右側にあるすべてのアイテムも目標よりも大きくなることがわかっています。これは、データの左側の部分だけを見る必要があることを意味します。基本的に、ターゲットを探して逃すたびに、残りのアイテムの半分を削除できます。これにより、素晴らしい O(log n) 時間の複雑さが得られます。

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

于 2010-09-18T06:50:31.790 に答える
5

線形検索は、値のリストの先頭から始まり、探している結果を確認するために1つずつチェックします。

バイナリ検索は、並べ替えられた配列の途中で開始され、探している値がどちら側にあるか（存在する場合）を判別します。次に、配列のその「半分」が同じ方法で再度検索され、結果が毎回2で半分に分割されます。

于 2009-03-31T06:26:24.513 に答える
2

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

二分検索は、ソートされたリストの中央から開始し、それが探している値よりも大きいか小さいかを調べることで、値がリストの前半または後半にあるかどうかを判断します。サブリストの途中までジャンプし、もう一度比較するなど。これは、人間が辞書で単語を検索する通常の方法とほぼ同じです (もちろん、より優れたヒューリスティックを使用しますが、「猫」を探している場合は、 「M」から始めます）。複雑さの点では、これは O(log n) 検索です。各操作で「検索スペース」が半分になるため、検索操作の数はリストよりもゆっくりと増加します。

于 2009-06-05T07:49:17.633 に答える
2

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

二分探索は、より大きな配列に対して効率的です。ここでは、中央の要素をチェックします。値が探しているものよりも大きい場合は、前半を調べます。そうでない場合は、後半を調べます。目的のアイテムが見つかるまでこれを繰り返します。テーブルは二分探索のためにソートする必要があります。各反復で半分のデータを削除します。対数です。

検索する要素が 1000 個ある場合、バイナリ検索には約 10 ステップ、線形検索には 1000 ステップかかります。

于 2009-03-31T06:43:58.170 に答える
2

二分探索は O(logn) 時間で実行されますが、線形検索は O(n) 回で実行されるため、二分探索の方がパフォーマンスが向上します。

于 2009-04-28T06:49:16.427 に答える
0

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

于 2017-05-25T12:21:23.540 に答える