線形探索: Python, C++ 例
サラ・チェン
検索アルゴリズムとは何ですか?
検索アルゴリズムは、特定のデータ構造を持つ要素またはオブジェクトのコレクションから要素またはオブジェクトを見つけるように設計されています。たとえば、指定された高さのリストから最小の高さを検索したり、数値のリストまたは配列から最高点を検索したりします。一般的な検索アルゴリズムには、「線形検索」、「バイナリ検索」、「ジャンプ検索」、「フィボナッチ検索」などがあります。
線形探索とは何ですか?
線形探索は最も単純な探索アルゴリズムの1つです。与えられたリストまたは配列から、与えられた要素を1つずつ検索します。線形探索はリスト全体を反復し、特定の要素が検索要素と等しいかどうかを確認します。線形探索は、 順次検索。
線形探索機能は何をするのですか?
整数の配列は「」として与えられます。Numbers、」、変数「item」には検索する整数が含まれます。
これで、線形検索アルゴリズムは次の出力を提供できます。
- 「-1」; これは、指定された要素が配列内に見つからないことを意味します
- 0 から n-1 までの任意の数値。 は、検索要素が見つかったことを意味し、配列上の要素のインデックスを返します。 ここで、「n」は配列のサイズを表します。
線形検索はどのように機能しますか?
整数を含む配列があるとします。タスクは、配列内で指定された数値を見つけることです。
- 数値が配列内にある場合は、その数値のインデックスを返す必要があります。
- 指定された数値が見つからない場合は、-1 を返します。
フローチャートでは、「データ」は整数配列、「N」は配列のサイズ、「項目」は配列内で検索する番号です。
線形探索アルゴリズムのフローチャート:
フローチャートの手順は次のとおりです。
ステップ1） 検索項目「アイテム」を読みます。
ステップ2） i=0 およびインデックス =-1 を開始します
ステップ3） もし私が
ステップ4） Data[i] が「item」と等しい場合は、ステップ 5 に進みます。そうでない場合は、ステップ 6 に進みます。
ステップ5） インデックス = i (項目はインデックス番号 i で見つかるため)。 手順 8 に進みます。
ステップ6） i = i +1。
ステップ7） 手順3に進みます。
ステップ8） 停止します。
簡単にするために、整数の配列を使用した例を示します。 線形検索は、文字列、オブジェクトの配列、または構造体にも適用できます。
逐次検索アルゴリズムの擬似コード
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 negative index is not valid return -1
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(arr[0]);
int item;
cout << "Enter a number to search: ";
cin >> item;
int idx = linearSearch(arr, 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 コード例 線形探索
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） データ[5]とデータ[4]を入れ替えます。 すると、データ配列は次のようになります。
データ [] = {1,5,9,8,4,7,3,11}
ここで、キーが検索される頻度が高くなるほど、インデックスが減少していることがわかります。 したがって、比較の数が減ります。
前に移動:
このメソッドでは、0 番目のインデックスの検索要素を交換します。 再度検索すると、O(1) 回で見つかるからです。
線形探索アルゴリズムの適用
ここでは、使用できる線形検索アプリケーションをいくつか紹介します。
- サイズが小さい配列、またはリスト内の要素が少数の場合は、線形検索を使用する方が簡単です。
- 線形探索法は単一または複数で使用できます。 多次元配列 または他のデータ構造。
- 一般に、線形検索は、「順序付けされていない」データの検索を実行するのに簡単で効率的です。 指定された順序なしリストから単一のデータを簡単にフェッチできます。