ক্ষুদ্রতম সূচক খুঁজে বের করার প্রোগ্রাম যার জন্য অ্যারে উপাদানটি পাইথনের সূচকের মতোই

ধরুন আমাদের কাছে সংখ্যা নামক উপাদানগুলির একটি তালিকা রয়েছে যেখানে সমস্ত আইটেম অনন্য, এবং সেগুলি আরোহী ক্রমে সাজানো হয়েছে, আমাদের ন্যূনতম i খুঁজে বের করতে হবে যেমন nums[i] =i। যদি আমরা কোন সমাধান খুঁজে না পাই, তাহলে -1 ফিরে আসুন। আমাদের এই সমস্যাটি O(log(n)) সময়ে সমাধান করতে হবে।

সুতরাং, ইনপুট যদি nums =[-4, -1, 2, 3, 8] এর মত হয়, তাহলে আউটপুট হবে 2, কারণ উভয় সংখ্যা[2] =2 এবং nums[3] =3 কিন্তু 2 ছোট।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ret :=-1, lhs :=0, rhs :=সংখ্যার আকার - 1

• যখন lhs <=rhs, do

  • mid :=(lhs + rhs) / 2

    এর তল

  • যদি nums[mid] মিডের সমান হয়, তাহলে

    • ret :=মধ্য

  • যদি nums[mid]>=mid, তারপর

    • rhs :=মধ্য - 1

  • অন্যথায়,

    • lhs :=মধ্য + 1

• রিটার্ন রিটার্ন

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

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