ソートされた整数と値のリストを使用する三項探索アルゴリズム関数を作成しようとしています。これは二分探索に似ていますが、反復ごとに 2 つのインデックス ind1 と ind2 (ind1 < ind2) を選択することにより、検索領域が 3 つの小さな領域 (可能な限り同じ長さ) に分割される点が異なります。
• リージョン 1 には、ind1 未満のインデックス値を持つすべてのアイテムが含まれます。
• リージョン 2 には、ind1 よりも大きく ind2 よりも小さいインデックス値を持つすべてのアイテムが含まれます。
• リージョン 3 には、ind2 より大きいインデックス値を持つすべてのアイテムが含まれます。
可能であれば、これらの領域のサイズは等しくする必要があります。これが不可能な場合、リージョン 1 のサイズはリージョン 2 のサイズ以上である必要があり、リージョン 2 のサイズはリージョン 3 のサイズ以上である必要があります。任意の 2 つのリージョンのサイズ最大で 1 つ異なる場合があります。
私が従おうとしている形式は次のとおりです。
検索領域のサイズが <= 4 の場合
v の線形検索を実行する
そうしないと
L[ind1] が v に等しい場合、インデックス ind1 と ind2 を選択します
やめて、v < L[ind1] の場合、v を見つけました。
L[ind2] が v に等しい場合は、領域 1 を新しい検索領域として繰り返します。
停止します。v を見つけました。それ以外の場合は v < L[ind2]
リージョン 2 を新しい検索リージョンとして繰り返します。
Region 3 を新しい検索領域として繰り返します
~~~~~
リストを検索するだけでなく、アルゴリズムがチェックするステップも生成する必要があります。
~~~~~
例えば：
ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,8 6,88,94], 88) は次のように出力する必要があります。
88 が 38 に等しいかどうかのチェック
88 が 38 より小さいかどうかのチェック
88 が 75 と等しいかどうかの確認
88 が 75 より小さいかどうかのチェック
88 が 81 と等しいかどうかのチェック
88 が 81 より小さいかどうかのチェック
88 が 88 と等しいかどうかのチェック
検索成功
88 はインデックス 17 にあります
全部で7回比較しました
~~~~~ 私が書いたコードは次のとおりです。
`def ternary_search (L, key):
left = 0
right = len(L) - 1
while left <= right:
ind1 = left
ind2 = left + (right - left) // 3
ind3 = left + 2 * (right - left) // 3
n = 0
if key == L[left]:
n += 1
print("Checking if " + str(key) + " is equal to " + str(left))
print("Search successful")
print(str(key) + " is located at index " + str(left))
print("A total of " + str(n) + " comparisons were made")
return
elif key == L[right]:
n += 1
print("Checking if " + str(key) + " is equal to " + str(right))
print("Search successful")
print(str(key) + " is located at index " + str(right))
print("A total of " + str(n) + " comparisons were made")
return
elif key < L[left] or key > L[right]:
n += 1
print("Search not successful")
print("A total of " + str(n) + " comparisons were made")
return
elif key <= L[ind2]:
n += 1
print("Checking if " + str(key) + " is less than " + str(L[ind2]))
right = ind2 -1
elif key > L[ind2] and key <= L[ind3]:
n += 1
print("Checking if " + str(key) + " is less than " + str(L[ind2]))
print("Checking if " + str(key) + " is equal to " + str(L[ind3]))
print("Checking if " + str(key) + " is less than " + str(L[ind3]))
left = ind2 + 1
right = ind3
else:
n += 1
print("Checking if " + str(key) + " is less than " + str(L[ind3]))
left = ind3 + 1
return`
私が電話するとき：
ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,86,88,94], 51)
それは印刷します：
Checking if 51 is less than 38
Checking if 51 is equal to 73
Checking if 51 is less than 73
Checking if 51 is less than 51
Search not successful
A total of 1 comparisons were made
印刷する必要がある場合:
Checking if 51 is equal to 38
Checking if 51 is less than 38
Checking if 51 is equal to 75
Checking if 51 is less than 75
Checking if 51 is equal to 53
Checking if 51 is less than 53
Checking if 51 is equal to 41
Checking if 51 is equal to 51
Search successful
51 is located at index 8
A total of 8 comparisons were made