सबसे छोटा सूचकांक खोजने का कार्यक्रम जिसके लिए सरणी तत्व भी पायथन में सूचकांक के समान है

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• ret :=-1, lhs :=0, rhs :=nums का आकार - 1

• जबकि lhs <=rhs, करते हैं

  • मध्य:=तल (एलएचएस + आरएचएस) / 2

  • यदि अंक [मध्य] मध्य के समान है, तो

    • रिट:=मध्य

  • अगर अंक [मध्य]>=मध्य, तो

    • 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