সূচী খোঁজার প্রোগ্রাম, যেখানে আমরা পাইথনে তালিকা সাজানোর জন্য উপাদান সন্নিবেশ করতে পারি

ধরুন আমাদের কাছে সংখ্যা নামক সংখ্যার একটি তালিকা আছে, সেগুলিকে ক্রমবর্ধমান ক্রমে সাজানো হয়েছে, আমাদের আরও একটি সংখ্যার লক্ষ্য আছে, আমাদের সূচকটি খুঁজে বের করতে হবে যেখানে সংখ্যাগুলিকে সাজানো রাখার জন্য লক্ষ্য সন্নিবেশ করা উচিত। যদি লক্ষ্য ইতিমধ্যেই সংখ্যায় উপস্থিত থাকে, তাহলে সবচেয়ে বড় সূচকটি ফেরত দিন যেখানে লক্ষ্য সন্নিবেশ করা যেতে পারে। আমাদের লাইব্রেরি ফাংশন ব্যবহার না করে এটি সমাধান করতে হবে এবং O(log n) সময়ে এটি সমাধান করতে হবে।

সুতরাং, যদি ইনপুটটি nums =[1,5,6,6,8,9] টার্গেট =6 এর মত হয়, তাহলে আউটপুট হবে 4, কারণ 6 ইতিমধ্যেই আছে, তাই এটি সন্নিবেশ করার জন্য, সবচেয়ে বড় সম্ভাব্য সূচকটি হল 4 , তাই অ্যারেটি হবে [1,5,6,6,6,8,9]।

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

• বামে :=0
• ঠিক :=
• সংখ্যার আকার - 1
• উত্তর :=0
• যখন বামে <=ডানে, কর
  • মাঝে :=তল (বাম + ডান) / 2
  • যদি টার্গেট>=সংখ্যা হয় [মিড], তাহলে
    • উত্তর :=মধ্য + 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