線形探索: Python, C++ 例:

検索アルゴリズムとは何ですか?

検索アルゴリズムは、特定のデータ構造を持つ要素またはオブジェクトの集合から、特定の要素またはオブジェクトを見つけるように設計されています。例えば、与えられた高さのリストから最小の高さを検索したり、数値のリストまたは配列から最高値を検索したりします。よく使われる検索アルゴリズムには、「線形探索」、「二分探索」、「ジャンプ探索」、「フィボナッチ探索」などがあります。

線形探索とは何ですか?

線形検索 は最も単純な検索アルゴリズムの 1 つです。与えられたリストまたは配列から、指定された要素を 1 つずつ検索します。線形検索はリスト全体を反復処理し、特定の要素が検索要素と等しいかどうかを確認します。これはまた、 逐次検索.

線形探索機能は何をするのですか?

整数の配列は「」として与えられます。Numbers、」、変数「item」には検索する整数が含まれます。

これで、線形検索アルゴリズムは次の出力を提供できます。

• 「-1」は、指定された要素が配列内に存在しないことを意味します。
• 0 から n-1 までの任意の数値。 は、検索要素が見つかったことを意味し、配列上の要素のインデックスを返します。 ここで、「n」は配列のサイズを表します。

線形検索はどのように機能しますか?

整数を含む配列があるとします。課題は、その配列の中から指定された数値を見つけることです。

• 数値が配列内にある場合は、その数値のインデックスを返す必要があります。
• 指定された数値が見つからない場合は、-1 を返します。

フローチャートでは、「データ」は整数配列、「N」は配列のサイズ、「項目」は配列内で検索する番号です。

線形探索アルゴリズムのフローチャート:

フローチャートの手順は次のとおりです。

ステップ1） 検索項目「アイテム」を読みます。

ステップ2） i=0、index=-1で初期化します。

ステップ3） もし私が

ステップ4） Data[i] が「item」と等しい場合は、ステップ 5 に進みます。そうでない場合は、ステップ 6 に進みます。

ステップ5） インデックス = i (項目はインデックス番号 i で見つかりました)。ステップ 8 に進みます。

ステップ6） i = i +1。

ステップ7） 手順3に進みます。

ステップ8） 停止します。

簡単にするために、整数の配列を使用した例を示します。 線形検索は、文字列、オブジェクトの配列、または構造体にも適用できます。

ニックネーム Code 逐次探索アルゴリズムの場合

以下の擬似コードは、上述の線形探索のロジックを表しています。配列を最初のインデックスから走査し、一致する要素が見つかった場合はその位置を返し、見つからない場合は -1 を返します。

function linearSearch: in → Data[], item
    foundAt = -1
    for i in (0 to data.length):
        if data[i] equals item:
            // item is found in the array
            // returning the index
            return i
    // item not found in the array
    // -1 means no item found, as a negative index is not valid
    return -1

C++ Code 線形探索の例

完全な C++ 逐次検索を実行し、検索された値のインデックスを出力するプログラム。

#include <bits/stdc++.h>
using namespace std;

int linearSearch(int *arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}

int main() {
    int array[] = {1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10};
    int n = sizeof(array) / sizeof(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

出力：

Enter a number to search: -10
-10 is found at index 14

Python Code 線形探索の例

同じ論理で Python リストのインデックスに対して単一のループを使用し、一致した要素の位置を返します。

def linearSearch(data, item):
    for i in range(len(data)):
        if data[i] == item:
            return i
    return -1

data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else:
    print("{} was not found".format(item))

出力：

Enter a number to search: -10
-10 is found at index 14

線形探索アルゴリズムの複雑性分析

一般的に、時間計算量とは、特定のタスクを実行するために必要なCPU時間を指します。線形探索アルゴリズムでは、配列の要素から検索キーを見つけることがタスクとなります。

時間の複雑さには次の 3 つの種類があります。

• 最悪のシナリオ
• ベストケースシナリオ
• 平均的なケースのシナリオ

最悪のシナリオにおける線形探索の時間計算量:

サイズが「n」の配列に対して線形探索を行う必要があるとしましょう。検索対象はインデックス0からn-1の間で見つけることができます。最悪の場合、アルゴリズムは配列内のすべての要素を検索対象要素と照合しようとします。

その場合、最悪の場合の計算量はO(n)になります。ここで、「O」（大文字O記法）は計算量関数を意味します。

最良のシナリオにおける線形探索の時間計算量:

配列の最初の位置にある要素を検索する場合を考えてみましょう。この場合、線形探索アルゴリズムは配列内のすべてのn個の要素を検索するわけではありません。したがって、計算量はO(1)となります。つまり、定数時間で処理が完了するということです。

平均的なケースのシナリオにおける線形探索の時間計算量:

配列の中央のインデックスで要素が見つかった場合、線形検索の平均ケース複雑度は O(N) であると言えます。ここで、N は配列の長さを意味します。

線形探索アルゴリズムの空間計算量：

線形探索の空間計算量は常にO(N)です。なぜなら、線形探索関数では一時変数を格納したり使用したりする必要がないからです。

線形検索アルゴリズムを改善する方法

プログラムのライフサイクル全体を通して検索を複数回実行できます。線形探索アルゴリズムを実行して特定のキーを複数回検索する可能性もあります。二分探索アルゴリズム” 配列がソートされた配列の場合。

配列が 10 万個の数字で構成され、ターゲット要素が 5000 番目のインデックスにあると仮定します。したがって、アルゴリズムは 5000 個の要素を比較しようとします。比較は CPU を大量に消費するタスクです。線形検索アルゴリズムを最適化するには、XNUMX つのオプションがあります。

• 転置
• 前に移動

移調:

この方法では、検索対象の要素を配列内の前の要素と交換します。例えば、次のような配列があるとします。

データ[] = {1,5,9,8,7,3,4,11}

ここで、4. 移調のステップを検索します。

ステップ1） 「4」はインデックス 6 で見つかります。XNUMX 回の比較が必要でした。

ステップ2） データ[6]とデータ[5]を入れ替えます。 データ配列は次のようになります。

データ[] = {1,5,9,8,7,4,3,11}

ステップ3） 4を再度検索します。 インデックス 5 で見つかりました。今回は XNUMX 回の比較が必要でした。

ステップ4） data[5]とdata[4]を入れ替えます。すると、データ配列は次のようになります。

データ[] = {1,5,9,8,4,7,3,11}

さて、お気づきかもしれませんが、キーの検索頻度が高くなるほど、インデックスの値は小さくなります。つまり、比較回数が減るということです。

前に移動:

この方法では、検索対象要素を0番目のインデックスに交換します。なぜなら、再度検索すればO(1)の時間で見つけることができるからです。

線形探索アルゴリズムの適用

ここでは、使用できる線形検索アプリケーションをいくつか紹介します。

• 配列のサイズが小さい場合や、リスト内の要素が少ない場合は、線形探索を使用する方が簡単です。
• 線形探索法は単一または複数で使用できます。 多次元配列 または他のデータ構造。
• 一般に、線形検索は、「順序付けされていない」データの検索を実行するのに簡単で効率的です。 指定された順序なしリストから単一のデータを簡単にフェッチできます。

よくあるご質問