最初に、与えられた配列に対して線形探索を行う方法を見てみましょう。線形探索では、配列を順番に見ていき、指定された要素が見つかったら位置を記録します。最初の位置を見つけた後は、その要素と異なる要素が見つかるまで配列を進め、最後の位置を記録します。以下に、このアプローチのコード例を示します。
def searchRange(nums, target):
first, last = -1, -1
for i in range(len(nums)):
if nums[i] == target:
if first == -1:
first = i
last = i
return [first, last]このコードでは、numsは与えられた配列、targetは探索する要素を表します。firstとlastは最初と最後の位置を記録するための変数です。配列を順番に見ていき、要素が見つかった場合には位置を更新します。最終的に、[first, last]の形式で最初と最後の位置を返します。
次に、二分探索を用いた効率的な方法を見てみましょう。配列がソートされている場合、二分探索を使うことで効率的に最初と最後の位置を見つけることができます。まず、二分探索を用いて指定された要素が存在するかどうかを判定し、存在する場合はその位置を記録します。その後、最初の位置を見つけるために指定された要素と異なる要素が見つかるまで、二分探索を行い、最後の位置を記録します。以下に、二分探索を用いたアプローチのコード例を示します。
def searchRange(nums, target):
first = binarySearch(nums, target, True)
last = binarySearch(nums, target, False)
return [first, last]
def binarySearch(nums, target, findFirst):
result = -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
result = mid
if findFirst:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return resultこのコードでは、binarySearch関数を定義して二分探索を行っています。findFirstパラメータは最初の位置を探すか最後の位置を探すかを指定するためのフラグです。二分探索を行いながら最初または最後の位置を記録し、最終的に[first, last]の形式で返します。