用 Python 编写程序，查找数组元素的最小索引，该索引也与索引相同

pythonserver side programmingprogramming更新于 2025/12/17 23:08:17

假设我们有一个名为 nums 的元素列表，其中所有项目都是唯一的，并且按升序排序，我们必须找到最小的 i，使得 nums[i] = i。如果我们找不到任何解决方案，则返回 -1。我们必须在 O(log(n)) 时间内解决这个问题。

因此，如果输入为 nums = [-4, -1, 2, 3, 8]，则输出将为 2，因为 nums[2] = 2 和 nums[3] = 3，但 2 较小。

要解决这个问题，我们将遵循以下步骤 −

ret := -1, lhs := 0, rhs := size of nums - 1
当 lhs <= rhs 时，执行
- mid := floor of (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))