পাইথনে সর্টেড লিস্টে এলিমেন্ট ইনসার্ট করার ইনডেক্স খুঁজে বের করার প্রোগ্রাম

পাইথনে একটি সর্টেড লিস্ট nums (ওর্ডমে) এবং একটি টার্গেট মান দেওয়া থাকলে, টার্গেটটি কোথায় ইনসার্ট করলে লিস্ট সর্টেড থাকবে সেটি বের করতে হবে। যদি টার্গেটটি ইতিমধ্যে লিস্টে থাকে, তবে সবচেয়ে বড় ইনডেক্স রিটার্ন করতে হবে (rightmost insertion point)। লাইব্রেরি ফাংশন ছাড়া O(log n) সময়ে সমাধান করতে হবে।

উদাহরণ

ইনপুট: nums = [1, 5, 6, 6, 8, 9], target = 6

আউটপুট: 4

কারণ ৬ ইতিমধ্যে আছে, সবচেয়ে ডানে ইনসার্ট করলে ইনডেক্স ৪ হবে: [1, 5, 6, 6, 6, 8, 9]

এলগরিদম (বাইনারি সার্চ - Upper Bound)

1. left := 0, right := len(nums) - 1, ans := 0
2. যখন left <= right:
   • mid := (left + right) // 2
   • যদি target >= nums[mid]:
     • ans := mid + 1
     • left := mid + 1 (ডান পাশে খুঁজুন)
   • অন্যথায়:
     • right := mid - 1 (বাম পাশে খুঁজুন)
3. ans রিটার্ন করুন

পাইথন ইমপ্লিমেন্টেশন

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))  # Output: 4

ইনপুট

[1, 5, 6, 6, 8, 9], 6

আউটপুট

4

ব্যাখ্যা

• এটি স্ট্যান্ডার্ড Upper Bound / bisect_right বাইনারি সার্চ।
• target >= nums[mid] কন্ডিশনটি নিশ্চিত করে যে সমান মান পাওয়া গেলেও ডান পাশে সার্চ চালানো হয়, ফলে সবচেয়ে ডানের ইনডেক্স मिलে।
• ans ভ্যারিয়েবলটি সার্চের সময় সম্ভাব্য ইনসার্শন পয়েন্ট ট্র্যাক করে।

পাইথন লাইব্রেরি সমতুল্য

import bisect
index = bisect.bisect_right(nums, target)  # Returns 4

বিএননারি সার্চ টেমপ্লেট: এই প্যাটার্নটি "প্রথম true বা শেষ false" খুঁজে বের করার জন্য বহুল ব্যবহৃত হয়।