インデックスを見つけるプログラム。Pythonでリストを並べ替えるための要素を挿入できます

numsと呼ばれる数値のリストがあり、それらが昇順でソートされているとします。また、別の数値ターゲットがあり、numsをソートし続けるためにターゲットを挿入するインデックスを見つける必要があります。ターゲットがすでにnumsで存在する場合は、ターゲットを挿入できる最大のインデックスを返します。ライブラリ関数を使用せずにこれを解決し、O（log n）時間で解決する必要があります。

したがって、入力がnums =[1,5,6,6,8,9] target =6のような場合、出力は4になります。これは、6がすでに存在するため、挿入する場合、可能な最大のインデックスは4です。 、したがって、配列は[1,5,6,6,6,8,9]のようになります。

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

• 左：=0
• 右：=
• numsのサイズ-1
• ans：=0
• 左<=右、実行
  • mid：=（左+右）の床/ 2
  • target> =nums [mid]の場合、
    • ans：=mid + 1
    • 左：=半ば+ 1
  • それ以外の場合、
    • 右：=半ば-1
• 回答を返す

例

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

def solve(nums, target):
   left, right = 0, len(nums) - 1
   ans = 0
   while left <= right:
      mid = (left + right) // 2
      if target >= nums[mid]:
         ans = mid + 1
         left = mid + 1
      else:
         right = mid - 1
   return ans

nums = [1,5,6,6,8,9]
target = 6
print(solve(nums, target))

入力

[1,5,6,6,8,9], 6

出力

4