配列内の要素を検索する Python プログラム
- 王林転載
- 2023-09-17 19:45:031145ブラウズ
Python では主に 2 つの検索アルゴリズムが主に使用されます。このうち、1 つ目は線形探索、2 つ目は二分探索です。
これら 2 つの手法は、指定された配列または指定されたリストから要素を検索するために主に使用されます。要素を検索する際には、どのような種類のアルゴリズムでも従うことができる 2 つの方法論があります。そのうちの 1 つは再帰的アプローチであり、もう 1 つは反復的アプローチです。両方のアプローチの両方のアルゴリズムについて説明し、同様の問題を解決しましょう。
線形検索
線形検索手法は、順次検索とも呼ばれます。 「シーケンシャル検索」という名前の意味は、この検索アルゴリズムが実行するプロセスによって明らかに正当化されます。これは、Python で配列またはリスト内の要素を見つけるために使用されるメソッドまたはテクニックです。
これは、他のすべての受信アルゴリズムの中で最も単純かつ最も簡単であると考えられています。しかし、このアルゴリズムの唯一の欠点は、効率が低いということです。
算法ステップ 1 -目的の要素と指定された配列に存在する各要素を比較するだけで、要素を順番に検索します。
ステップ 2- - 必要な要素が見つかった場合は、要素のインデックスまたは位置がユーザーに表示されます。
ステップ 3
-要素が配列内に存在しない場合、要素が見つからないことがユーザーに通知されます。このようにしてアルゴリズムが処理されます。 -
一般に、線形検索アルゴリズムは、各要素をチェックして比較するため、サイズが 100 以下の小さな配列または小さなリストに比較的適しており、効率的です。
##平均的な場合の線形探索アルゴリズムの時間計算量は「 O( n ) 」です。この場合、要素は配列の中間位置に存在します。つまり、インデックス「 ( n – 1 ) / 2 」または「 (( n – 1 ) / 2 ) 1 」が付けられます。
線形探索アルゴリズムの最悪の場合の時間計算量は「O( n ) 」です。この場合、要素は配列の最後の位置、つまりインデックス「 n-1 」で存在します。
-
＃＃＃例＃＃＃
以下の例では、数値グループ内の要素を抽出するプロセスを物理的に使用します。 リーリー ＃＃＃出力＃＃＃
上記手順の出力例：
リーリー
- 例 (再帰的)
以下の例では、数グループ内での線形検索のプロセスを学術的に使用します。 リーリー ＃＃＃出力＃＃＃ 上記手順の出力例：
二分探索
二分法は、シーケンス内の要素を取り出すためにまったく異なる手順に従います。
何らかの状況で数値グループが順序付けされていない場合、その数値グループは順序付けされ、その後、その数値グループに適用されるプロセスが開始されます。算法
ステップ 1
- 数値グループの順序付けが最初のステップです。
ステップ 2-配列が並べ替えられた後、配列は 2 つの半分とみなされます。半分はソートされた配列の最初の要素から中間の要素まで始まり、後半はソートされた配列の中央の要素の次の要素から最後の要素まで始まります。
ステップ 3
-キー要素 (検索対象の要素はキー要素と呼ばれます) が、並べ替えられた配列の中央の要素と比較されます。
ステップ 4- -キー要素が並べ替えられた配列の中央の要素以下の場合、キー要素は中央の要素より小さいため、後半の要素はさらに無視されます。したがって、この要素は最初の要素と中間の要素の間に必ず存在する必要があります。
-
ステップ 6 -キー要素が中央の要素より大きい場合、並べ替えられた配列の前半は無視され、中央の要素から最後の要素までの要素が考慮されます。 -
ステップ 7 -これらの要素のうち、キー要素が再び半分の配列の中央の要素と比較され、同じ手順を繰り返します。キー要素が半分にされた配列の中央の要素より大きい場合、前半は無視されます。 第8步 - 如果关键元素小于或等于被分割数组的中间元素，则被分割数组的后半部分将被忽略。通过这种方式，元素将在数组的任意一半中进行搜索。
因此，与线性搜索相比，复杂度减少了一半或更多，因为有一半的元素将在第一步中被移除或不被考虑。二分搜索的最佳情况时间复杂度为“O(1)”。二分搜索的最坏情况时间复杂度为“O(logn)”。这就是二分搜索算法的工作原理。让我们考虑一个例子，并应用二分搜索算法来找出数组中的关键元素。
Example
In this example, we are going to learn about the process of searching an element in an array using Binary search in recursive approach.
def recursive_binary(arr, first, last, key_element):
if first <= last:
mid = (first + last) // 2
if arr[mid] == key_element:
return mid
elif arr[mid] > key_element:
return recursive_binary(arr, first, mid - 1, key_element)
elif arr[mid] < key_element:
return recursive_binary(arr, mid + 1, last, key_element)
else:
return -1
arr = [20, 40, 60, 80, 100]
key = 80
max_size = len(arr)
result = recursive_binary(arr, 0, max_size - 1, key)
if result != -1:
print("The element", key, "is present at index", (result), "in the position", (result + 1))
else:
print("The element is not present in the array")
Output
上述程序的输出如下：
The element 80 is found at the index 3 and in the position 4
Example
In this example, we are going to learn about the process of searching an element in an array using Binary search in iterative approach.
def iterative_binary(arr, last, key_element):
first = 0
mid = 0
while first <= last:
mid = (first + last) // 2
if arr[mid] < key_element:
first = mid + 1
elif arr[mid] > key_element:
last = mid - 1
else:
return mid
return -1
arr = [20, 40, 60, 80, 100]
key = 80
max_size = len(arr)
result = iterative_binary(arr, max_size - 1, key)
if result != -1:
print("The element", key, "is present at index", (result), "in the position", (result + 1))
else:
print("The element is not present in the array")
Output
上述程序的输出如下：
The element 80 is found at the index 3 and in the position 4
这是二分搜索算法的工作原理。根据时间复杂度的概念，我们可以肯定二分搜索算法比线性搜索算法更高效，时间复杂度在其中起着重要的作用。通过使用这种类型的算法，可以搜索数组中的元素。尽管用于解决问题的过程不同，但结果不会波动。这是使用多种算法检查输出一致性的一个优点。
以上が配列内の要素を検索する Python プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。