पायथन में सबसे छोटा इंडेक्स ढूंढना जिसके लिए ऐरे तत्व इंडेक्स के समान हो

मान लीजिए हमारे पास nums नामक तत्वों की एक लिस्ट है जहां सभी आइटम यूनिक हैं, और वे आरोही क्रम में सॉर्टेड हैं, हमें न्यूनतम i ढूंढना है जैसे कि nums[i] = i। यदि हम कोई समाधान नहीं ढूंढ सकते, तो -1 लौटाएं। हमें इस समस्या को O(log(n)) समय में हल करना है।

उदाहरण के लिए, यदि इनपुट है nums = [-4, -1, 2, 3, 8], तो आउटपुट होगा 2, क्योंकि nums[2] = 2 और nums[3] = 3 दोनों हैं लेकिन 2 छोटा है।

समाधान दृष्टिकोण

चूंकि ऐरे सॉर्टेड है और तत्व यूनिक हैं, फंक्शन f(i) = nums[i] - i नॉन-डिक्रीजिंग है। बाइनरी सर्च का उपयोग करके सबसे छोटा i ढूंढें जहां f(i) == 0।

• ret = -1, lhs = 0, rhs = len(nums) - 1 आरंभ करें।
• जब lhs <= rhs:
  • mid = (lhs + rhs) // 2।
  • यदि nums[mid] == mid, तो ret = mid।
  • यदि nums[mid] >= mid, तो rhs = mid - 1 (बाएं खोजें)।
  • अन्यथा lhs = mid + 1 (दाएं खोजें)।
• 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))

इनपुट

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

आउटपुट

2