सूचकांक खोजने के लिए कार्यक्रम, जहां हम सूची को पायथन में क्रमबद्ध रखने के लिए तत्व सम्मिलित कर सकते हैं

मान लीजिए हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है, उन्हें आरोही क्रम में क्रमबद्ध किया जाता है, हमारे पास एक और संख्या लक्ष्य भी होता है, हमें वह सूचकांक खोजना होता है जहां अंकों को क्रमबद्ध रखने के लिए लक्ष्य डाला जाना चाहिए। यदि लक्ष्य पहले से ही अंकों में मौजूद है, तो सबसे बड़ा सूचकांक लौटाएं जहां लक्ष्य डाला जा सकता है। हमें इसे पुस्तकालय कार्यों का उपयोग किए बिना हल करना होगा और इसे ओ (लॉग एन) समय में हल करना होगा।

इसलिए, यदि इनपुट संख्या =[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