मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, वे आरोही क्रम में सॉर्टेड हैं, हमारे पास एक और संख्या target है, हमें वह इंडेक्स ढूंढना है जहां target को डालने से nums सॉर्टेड रहे। यदि target पहले से ही nums में मौजूद है, तो सबसे बड़ा इंडेक्स लौटाएं जहां target डाला जा सकता है। हमें इसे लाइब्रेरी फ़ंक्शन का उपयोग किए बिना और O(log n) समय में हल करना है।
इसलिए, यदि इनपुट है nums = [1,5,6,6,8,9] target = 6, तो आउटपुट 4 होगा, क्योंकि 6 पहले से ही वहां है, इसलिए इसे डालने के लिए सबसे बड़ा संभव इंडेक्स 4 है, तो सरणी [1,5,6,6,6,8,9] जैसी होगी।
हल करने का दृष्टिकोण
- left := 0
- right := nums का आकार - 1
- ans := 0
- जब तक left <= right, करें:
- mid := (left + right) / 2 का फ्लोर
- यदि target >= nums[mid], तो:
- ans := mid + 1
- left := mid + 1
- अन्यथा:
- right := mid - 1
- 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))इनपुट
[1,5,6,6,8,9], 6
आउटपुट
4
