Python での検索アルゴリズムの実装

検索の実装は常に困難ですが、不可能ではありません。

現実世界では、ノーパターンで検索します。置いてありそうな場所に行くだけです。ほとんどの場合、どのようなパターンにも従いません。

プログラミングの世界でも同じことが当てはまるでしょうか?

いいえ！プログラム内で検索するには、何らかのパターンが必要です。この記事では、さまざまな検索パターンに従うアルゴリズムをいくつか見ていきます。

プログラミングの世界には複数のアルゴリズムがあります。この記事では、最も重要でよく使用されるアルゴリズムについて説明します。残りのアルゴリズムは簡単に学ぶことができます。

この記事では、検索とは 配列内の要素を検索すること を指します。

一つずつ見ていきましょう。

線形探索

この名前は、 線形検索アルゴリズムが 線形 パターン に従って配列内の要素を検索することを示唆しています。アルゴリズムは配列の先頭から要素の検索を開始し、要素が見つかるまで末尾に移動します。必要な要素が見つかるとプログラムの実行を停止します。

アルゴリズムをよりよく理解するために 、線形検索アルゴリズムを いくつかのクールな図で説明しましょう。

検索パターンを注意深く観察すると、プログラムの実行にかかる時間は 最悪の場合 でも O(n) かかることがわかります。分析するアルゴリズムの最悪の場合の時間計算量を考慮する必要があります。したがって、アルゴリズムの時間計算量は O(n) です。

線形探索アルゴリズムの実装を見てみましょう。

線形検索の実装

これで、線形探索アルゴリズムについてよく理解できました。コードを使って手を汚す時が来ました。まず、線形検索を実装する手順を見てみましょう。次に、それをコーディングしてみます。たとえできなくても心配しないでください。後ほどコードをご案内させていただきます。

線形探索アルゴリズムを実装する手順を見てみましょう。

• 要素の配列 (幸運な数字) を初期化します。
• search_element という関数を作成します。 この関数は、配列、配列の長さ、検索する要素の 3 つの引数を受け取ります。
• 検索要素(arr, n, 要素):
  • 指定された配列を反復処理します。
    • 現在の要素が必要な要素と等しいかどうかを確認します。
    • 「はい」の場合は、 True を返します。
  • ループの完了後、実行がまだ関数内にある場合、要素は配列内に存在しません。したがって、 False を返します。
• 関数 search_element の戻り値に基づいてメッセージを出力します。

最後に、上記の手順を使用してコードを作成し、線形検索アルゴリズムを実装します。

線形探索アルゴリズムの実装は完了しましたか?そうだといい。完了したら、次のコードでクロスチェックを行います。

完了していなくても心配しないでください。以下のコードを参照して、それをどのように実装したかを学習してください。それほど苦労せずに取得できます。

 ## searching function
def search_element(arr, n, element):

	## iterating through the array
	for i in range(n):

		## checking the current element with required element
		if arr[i] == element:
			## returning True on match
			return True

	## element is not found hence the execution comes here
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 6
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

まず、配列内に存在する要素を使用してプログラムを実行します。次に、配列に存在しない要素を使用して実行します。

線形探索アルゴリズムの時間計算量は O(n) です。

別のパターンでもう少し減らすことはできますか?

はい、できます。それを見てみましょう。

二分探索

二分探索アルゴリズムは 常に配列の中央の要素をチェックします。このアルゴリズムは、 ソートされた配列 内の要素を検索します。

二分探索アルゴリズムは 配列を反復処理し、中央の要素をチェックし、見つかった場合はプログラムを停止します。それ以外の場合、中央の要素が必要な要素より小さい場合は、中央の要素の配列の左側の部分が検索から除外されます。それ以外の場合、中央の要素が必要な要素よりも大きい場合は、中央の要素から配列の右側の部分が検索から除外されます。

各反復で、二分探索アルゴリズムは要素を検索する領域を削減します。したがって、チェックの数は、線形探索アルゴリズムで行われるチェックの数よりも少なくなります。

図は、 二分探索アルゴリズムを より深く理解するのに役立ちます。それらを確認してみましょう。

二分探索アルゴリズムの時間計算量は O(log n) です。各反復で、検索領域の長さは半分に減少します。指数関数的に減少しています。

二分探索の実装

まず、二分探索アルゴリズムを実装する手順を見てから、コードを見ていきます。二分探索アルゴリズムの実装を完了する手順を見てみましょう。

• 配列を要素 (ラッキーナンバー) で初期化します。
• search_element という関数を作成します。 この関数は、ソートされた配列、配列の長さ、検索する要素の 3 つの引数を受け取ります。
• search_element(sorted_arr, n, element):
  • 配列の反復用にインデックス変数 i を初期化します。
  • 次に、配列の検索領域を維持するために 2 つの変数を初期化します。ここでは、インデックスを示すため、 開始 と 終了 と呼びます。
  • i が 配列の長さより小さくなるまで繰り返します。
    • 開始値 と 終了 値を使用して、検索領域の中間インデックスを計算します。それは (start + end) // 2 になります。
    • 検索領域の中央のインデックス付き要素が必要な要素と等しいかどうかを確認します。
    • 「はい」の場合は、 True を返します。
    • それ以外の場合、中央のインデックス付き要素が必要な要素より小さい場合は、検索領域の 開始 インデックスを middle + 1 に移動します。
    • それ以外の場合、中央のインデックス付き要素が必要な要素より大きい場合は、検索領域の 終了 インデックスを middle – 1 に移動します。
    • 配列 i のインデックスをインクリメントします。
  • ループの完了後、実行がまだ関数内にある場合、要素は配列内に存在しません。したがって、 False を返します。
• 関数 search_element の戻り値に基づいてメッセージを出力します。

線形探索アルゴリズムの実装と同様のコードを作成してみてください。

…

コードを取得しましたか?

はい、以下のコードと比較してください。いいえ、心配しないでください。以下のコードの実装を理解してください。

 ## searching function
def search_element(sorted_arr, n, element):

	## array index for iteration
	i = 0

	## variables to track the search area
	## initializing them with start and end indexes
	start = 0
	end = n - 1

	## iterating over the array
	while i < n:
		## getting the index of the middle element
		middle = (start + end) // 2

		## checking the middle element with required element
		if sorted_arr[middle] == element:
			## returning True since the element is in the array
			return True
		elif sorted_arr[middle] < element:
			## moving the start index of the search area to right
			start = middle + 1
		else:
			## moving the end index of the search area to left
			end = middle - 1
		i += 1
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 9
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

要素が存在する場合と存在しない場合のさまざまなケースでコードをテストします。

結論

二分探索アルゴリズムは、 線形探索アルゴリズム よりもはるかに効率的です。二分探索アルゴリズムでは配列をソートする必要がありますが、線形探索アルゴリズムの場合はそうではありません。並べ替えには時間がかかります。ただし、ソートに効率的なアルゴリズムを使用すると、二分探索アルゴリズムと適切に組み合わせることができます。

これで、Python で最も広く使用されているアルゴリズムについて十分な知識が得られました。

次に、人気のあるセルフホスト検索ソフトウェアをいくつか見つけてください。

コーディングを楽しんでください 🙂 🧑‍💻