こちらは「Search Insert Position」のPythonによる解答例となっております。この問題は、ソートされた整数の配列とターゲットの数値が与えられたときに、配列内にターゲットが存在する場合はそのインデックスを返し、存在しない場合は挿入されるべきインデックスを返す問題です。
問題
整数の配列 nums とターゲット値 target が与えられたとき、targetが配列 nums 内に存在する場合、そのインデックスを返します。存在しない場合は、targetが挿入されるべきインデックスを返します。
- 配列
numsはソートされていると仮定します。 10^4以下の長さの配列numsが与えられます。10^4以上の整数nums[i]が与えられます。10^4以上の整数targetが与えられます。numsには重複がないと仮定されます。
解法
この問題は、2分探索を用いた1つのアプローチがあります。ソートされた配列内でターゲット要素を探す際には、2分探索が有効です。2分探索は、配列を対象の範囲を半分に繰り返し分割して探索する方法で、線形探索よりも速く探索できます。
アルゴリズムの概要を以下に示します。
- 配列の中央の要素を取得します。
- 中央の要素がターゲットと等しい場合、中央のインデックスを返します。
- 中央の要素がターゲットよりも大きい場合、配列の左側を再帰的に探索します。
- 中央の要素がターゲットよりも小さい場合、配列の右側を再帰的に探索します。
- ターゲットが存在しない場合、ターゲットが挿入されるべきインデックスを返します。
Pythonコード
以下のコードが、「Search Insert Position」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().searchInsert
if 1 <= num <= Input().input: id_LIST = [num]
else: id_LIST = [id+1 for id in range(Input().input)]
for id in id_LIST:
data = Input(id)
ans = solver(data.nums, data.target)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
import bisect
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
return bisect.bisect_left(nums,target)
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.nums = [1,3,5,6]
self.target = 5
self.ans = 2
elif num == 2:
self.nums = [1,3,5,6]
self.target = 2
self.ans = 1
elif num == 3:
self.nums = [1,3,5,6]
self.target = 7
self.ans = 4
else:
self.input = 3
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################