পাইথনে সোর্টেড ইউনিক অ্যারে-এ nums[i] == i হলে স্মলেস্ট ইন্ডেক্স বের করার প্রোগ্রাম (O(log n))

একটি সোর্টেড ইউনিক লিস্ট nums দেওয়া আছে। ন্যূনতম i বের করুন যাতে nums[i] == i। না পেলে -1। O(log n) টাইমে সমাধান করুন।

উদাহরণ

nums = [-4, -1, 2, 3, 8] → আউটপুট: 2

nums[2]=2 এবং nums[3]=3 — ২ ছোট।

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

1. ret := -1, lhs := 0, rhs := len(nums)-1
2. while lhs <= rhs:
   • mid := (lhs + rhs) // 2
   • যদি nums[mid] == mid: ret := mid
   • যদি nums[mid] >= mid: rhs := mid - 1
   • অন্যথায়: lhs := mid + 1
3. 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))  # আউটপুট: 2

ইনপুট / আউটপুট

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