配列要素もPythonのインデックスと同じである最小のインデックスを見つけるプログラム

すべてのアイテムが一意であるnumsという要素のリストがあり、それらが昇順で並べ替えられているとすると、nums [i]=iとなる最小のiを見つける必要があります。解決策が見つからない場合は、-1を返します。この問題はO（log（n））時間で解決する必要があります。

したがって、入力がnums =[-4、-1、2、3、8]の場合、nums [2]=2とnums[3]=3の両方が小さいため、出力は2になります。

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

• ret：=-1、lhs：=0、rhs：=numsのサイズ-1

• lhs <=rhs、do

  • mid：=（lhs + rhs）/ 2

    のフロア

  • nums [mid]がmidと同じ場合、

    • ret：=mid

  • nums [mid]> =midの場合、

    • rhs：=mid-1

  • それ以外の場合

    • lhs：=mid + 1

• retを返す

例

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

def solve(nums):
   ret = -1
   lhs = 0
   rhs = len(nums) - 1
   while lhs <= rhs:
      mid = (lhs + rhs) // 2
      if nums[mid] == mid:
         ret = mid
      if nums[mid] >= mid:
         rhs = mid - 1
      else:
         lhs = mid + 1
   return ret

nums = [-4, -1, 2, 3, 8]
print(solve(nums))

入力

[-4, -1, 2, 3, 8]

出力

2