Chương trình tìm chỉ mục nhỏ nhất cho phần tử mảng nào cũng giống như chỉ mục trong Python

Giả sử chúng ta có một danh sách các phần tử được gọi là num trong đó tất cả các mục là duy nhất và chúng được sắp xếp theo thứ tự tăng dần, chúng ta phải tìm i nhỏ nhất sao cho nums [i] =i. Nếu chúng ta không thể tìm thấy bất kỳ giải pháp nào, thì trả về -1. Chúng ta phải giải quyết vấn đề này trong thời gian O (log (n)).

Vì vậy, nếu đầu vào giống như nums =[-4, -1, 2, 3, 8], thì đầu ra sẽ là 2, vì cả nums [2] =2 và nums [3] =3 nhưng 2 nhỏ hơn.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=-1, lhs:=0, rhs:=size of nums - 1

• trong khi lhs <=rhs, làm

  • giữa:=tầng của (lhs + rhs) / 2

  • nếu nums [mid] giống với mid thì

    • ret:=mid

  • if nums [mid]> =mid, then

    • rhs:=mid - 1

  • nếu không,

    • lhs:=mid + 1

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn

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))

Đầu vào

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

Đầu ra

2