Pythonでソートされた配列の要素の最初と最後の位置を見つける

整数Aの配列があるとします。これは昇順で並べ替えられ、指定されたターゲット値の開始位置と終了位置を見つける必要があります。配列内にターゲットが見つからない場合は、[-1、-1]を返します。したがって、配列が[2,2,2,3,4,4,4,4,5,5,6]のようで、ターゲットが4の場合、出力は[4,7]

これを解決するには、次の手順に従います-

• 最初はres：=[-1、-1]、low：=0、high：=配列Aの長さに設定
• 低い<高い
  • 中：=低+（高–低）/ 2
  • A [mid]がターゲットの場合、
    • high：=mid、res [0]：=mid、res [1]：=mid
  • それ以外の場合、A [mid] <ターゲットの場合、次にlow：=mid + 1、それ以外の場合はhigh：=mid
• res [0] =-1の場合、resを返します
• 低：=res [0] + 1、高：=数値の長さ
• 低い<高い
  • 中：=低+（高–低）/ 2
  • A [mid]がターゲットの場合、
    • low：=mid + 1、res [1]：=mid
  • それ以外の場合、A [mid] <ターゲットの場合、次にlow：=mid + 1、それ以外の場合はhigh：=mid
• return res

例（Python）

理解を深めるために、次の実装を見てみましょう-

class Solution(object):
   def searchRange(self, nums, target):
      res = [-1,-1]
      low = 0
      high = len(nums)
      while low<high:
         mid = int(low + (high-low)//2)
         if nums[mid] == target:
            high = mid
            res[0]=mid
            res[1]=mid
         elif nums[mid]<target:
            low = mid+1
         else:
            high = mid
      if res[0] == -1:
         return res
      low = res[0]+1
      high = len(nums)
      while low<high:
         mid = int(low + (high-low)//2)
         if nums[mid] == target:
            low = mid+1
            res[1] = mid
         elif nums[mid] < target:
            low = mid + 1
         else:
            high = mid
      return res
ob1 = Solution()
print(ob1.searchRange([2,2,2,3,3,4,4,4,4,5,5,6], 4))

入力

[2,2,2,3,4,4,4,4,5,5,6]
4

出力

[5, 8]