निचली सीमा और ऊपरी सीमा
bisect_left और bisect_right को शुरुआत से लागू कीजिए, फिर उनका उपयोग लक्ष्य मान की पहली और अंतिम स्थिति खोजने में कीजिए।
निचली सीमा और ऊपरी सीमा, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
निम्न और ऊपरी सीमाएँ क्या हैं
क्रमबद्ध सरणी में किसी लक्ष्य मान की निम्न सीमा उस पहले तत्व का सूचकांक है जो लक्ष्य से बड़ा या उसके बराबर हो (इसे अक्सर bisect_left कहा जाता है)। ऊपरी सीमा उस पहले तत्व का सूचकांक है जो लक्ष्य से सख्ती से बड़ा हो (bisect_right)। दोनों मिलकर लक्ष्य की हर उपस्थिति को घेरते हैं और O(log n) परास-प्रश्नों को संभव बनाते हैं।
ये दोनों संक्रियाएँ साक्षात्कार की कई समस्याओं का आधार हैं: उपस्थितियों की संख्या गिनना, परास ढूँढ़ना, सम्मिलन स्थान ढूँढ़ना और अन्य कार्य।
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)निम्न सीमा लागू करना (bisect_left)
bisect_left(arr, x) ऐसा सबसे बायाँ सूचकांक i लौटाता है जिसके लिए arr[i] >= x हो, या यदि सभी तत्व छोटे हों तो len(arr) लौटाता है। इसके कार्यान्वयन में ऊपरी सीमा को शामिल नहीं किया जाता: hi = len(arr), लूप की शर्त lo < hi होती है, और जब arr[mid] >= x हो तो hi = mid किया जाता है। इससे परिणाम सबसे बाईं वैध स्थिति तक पहुँचता है।
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4ऊपरी सीमा लागू करना (bisect_right)
bisect_right(arr, x) ऐसा सबसे बायाँ सूचकांक i लौटाता है जिसके लिए arr[i] > x हो। bisect_left से केवल एक पंक्ति अलग है: शर्त arr[mid] < x से बदलकर arr[mid] <= x हो जाती है। जब arr[mid] <= x हो, तो परिणाम mid के ठीक दाईं ओर होता है, इसलिए हम lo = mid + 1 करते हैं; अन्यथा दाईं ओर से परास को छोटा करते हैं।
def bisect_right(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1 # arr[mid] <= x, so answer is strictly right
else:
hi = mid
return lo
arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2)) # 4
print(bisect_right(arr, 0)) # 0
print(bisect_right(arr, 5)) # 6
print(bisect_right(arr, 4)) # 5दोनों सीमाओं से उपस्थितियों की संख्या गिनना
क्रमबद्ध सरणी में किसी लक्ष्य की उपस्थितियों की संख्या O(log n) में गिनने के लिए दोनों सीमाओं का उपयोग करें: count = bisect_right(arr, target) - bisect_left(arr, target)। यदि count 0 है, तो लक्ष्य मौजूद नहीं है। यह रैखिक जाँच से काफी तेज़ है और क्रमबद्ध डेटा पर बारंबारता संबंधी प्रश्नों के लिए मानक तरीका है।
import bisect
def count_occurrences(arr, target):
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2)) # 3
print(count_occurrences(arr, 3)) # 2
print(count_occurrences(arr, 4)) # 0
print(count_occurrences(arr, 1)) # 1लक्ष्य का पहला और अंतिम स्थान ढूँढ़ना
LeetCode 34 'क्रमबद्ध सरणी में तत्व का पहला और अंतिम स्थान ढूँढ़ें' में आपसे O(log n) में [first_idx, last_idx] लौटाने को कहा जाता है। पहला स्थान bisect_left(arr, target) है — लेकिन केवल तभी जब arr[result] == target हो। अंतिम स्थान bisect_right(arr, target) - 1 है। यदि इनमें से कोई जाँच विफल हो, तो [-1, -1] लौटाएँ।
import bisect
def search_range(nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
print(search_range([5,7,7,8,8,10], 8)) # [3, 4]
print(search_range([5,7,7,8,8,10], 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]सम्मिलन स्थान (LeetCode 35)
LeetCode 35 'सम्मिलन स्थान खोजें' पूछता है: सरणी को क्रमबद्ध बनाए रखने के लिए लक्ष्य को कहाँ डाला जाएगा? यह ठीक bisect_left(arr, target) है। यदि लक्ष्य मौजूद है, तो bisect_left उसका सूचकांक लौटाता है। यदि वह मौजूद नहीं है, तो bisect_left वह सूचकांक लौटाता है जहाँ उसे डाला जाना चाहिए। किसी विशेष अलग व्यवस्था की आवश्यकता नहीं है — यही फ़ंक्शन दोनों स्थितियों को संभालता है।
import bisect
def searchInsert(nums, target):
return bisect.bisect_left(nums, target)
print(searchInsert([1,3,5,6], 5)) # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2)) # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7)) # 4 (would append at end)
print(searchInsert([1,3,5,6], 0)) # 0 (would prepend)bisect_left और bisect_right के बीच अंतर
जब कोई दोहराए गए तत्व नहीं होते, तब bisect_left और bisect_right एक ही सूचकांक लौटाते हैं। अंतर तभी महत्वपूर्ण होता है जब लक्ष्य कई बार दिखाई देता है। bisect_left पहली प्रति पर पहुँचता है; bisect_right अंतिम प्रति के एक स्थान बाद पहुँचता है। हमेशा इस आधार पर चुनें कि आप मौजूदा प्रतियों से पहले सम्मिलन करना चाहते हैं (बाएँ) या बाद में (दाएँ)।
import bisect
arr = [1, 2, 2, 2, 3]
# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2)) # 1
# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2)) # 4
# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5)) # 4
print(bisect.bisect_right(arr, 2.5)) # 4क्रमबद्ध बारंबारता-प्रश्नों पर सीमाएँ लागू करना
जब आपको क्रमबद्ध सरणी पर अनेक परास-बारंबारता प्रश्नों के उत्तर कुशलतापूर्वक देने हों, तो सरणी को एक बार पहले से क्रमबद्ध कर लें और प्रत्येक प्रश्न के लिए द्विभाजन का उपयोग करें। प्रत्येक प्रश्न का उत्तर O(log n) में मिल जाता है — O(n) में नहीं — कि [lo, hi] में कितने तत्व आते हैं। यह तरीका क्रमबद्ध करने के बाद किसी मान-परास के भीतर तत्वों की संख्या गिनने वाली समस्याओं में दिखाई देता है।
import bisect
def count_in_range(arr, lo, hi):
'''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
left = bisect.bisect_left(arr, lo)
right = bisect.bisect_right(arr, hi)
return right - left
arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr) # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5)) # 6 (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2)) # 3 (1,1,2)मनमानी कुंजी से द्विआधारी search
कभी-कभी search कुंजी स्वयं संग्रहीत मान नहीं, बल्कि कोई व्युत्पन्न गुण होती है। पाइथन का द्विभाजन मॉड्यूल सीधे कुंजी फ़ंक्शन का समर्थन नहीं करता, लेकिन आप लूप के भीतर कुंजी लागू करके स्वयं द्विआधारी search कर सकते हैं। यह तरीका तब उपयोगी होता है जब किसी सूची की वस्तुओं को उनके किसी एक गुण के आधार पर खोजा जाता है।
# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
lo, hi = 0, len(records)
while lo < hi:
mid = lo + (hi - lo) // 2
if records[mid][0] < min_score:
lo = mid + 1
else:
hi = mid
return lo
records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx) # 1 (first record with score >= 72)
print(records[idx:]) # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]सीमाओं से जुड़ी साक्षात्कार की सामान्य त्रुटियाँ
सबसे सामान्य गलती bisect_left चलाने के बाद परिणाम की जाँच करना भूल जाना है। फ़ंक्शन हमेशा एक वैध सम्मिलन सूचकांक लौटाता है, लेकिन यह गारंटी नहीं देता कि उस सूचकांक का तत्व लक्ष्य के बराबर है। यह मान लेने से पहले कि लक्ष्य मिल गया है, हमेशा arr[result] == target जाँचें।
दूसरी गलती पहला उदाहरण चाहिए होने पर bisect_right का उपयोग करना है — bisect_right अंतिम उपस्थिति के एक स्थान बाद का सूचकांक लौटाता है, इसलिए 1 घटाने पर पहला नहीं, अंतिम स्थान मिलता है।
import bisect
arr = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx) # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found) # Falseसारांश: bisect_left और bisect_right का उपयोग कब करें
bisect_left का उपयोग तब करें जब आपको लक्ष्य की पहली उपस्थिति, ऐसा सम्मिलन-बिंदु जो मौजूदा प्रतियों को दाईं ओर खिसका दे, या यह जाँच चाहिए कि लक्ष्य मौजूद है। bisect_right का उपयोग तब करें जब आपको अंतिम उपस्थिति के एक स्थान बाद का सूचकांक, सभी मौजूदा प्रतियों के बाद का सम्मिलन-बिंदु, या लक्ष्य से छोटे या बराबर तत्वों की संख्या चाहिए (यह bisect_right(arr, target) के बराबर होती है)।
दोनों O(log n) में चलते हैं और पाइथन के मानक पुस्तकालय का हिस्सा हैं, इसलिए साक्षात्कारकर्ता द्वारा शुरू से लागू करने को कहे जाने तक आप इन्हें सीधे आयात करके उपयोग कर सकते हैं।
त्वरित जाँच
इस पाठ में डेटा संरचनाओं और एल्गोरिदम — कोडिंग साक्षात्कार की तैयारी की अवधारणाओं के बारे में अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: bisect_left लक्ष्य से बड़ा या उसके बराबर पहला तत्व ढूँढ़ता है, bisect_right लक्ष्य से बड़ा पहला तत्व ढूँढ़ता है (अंतिम उपस्थिति के एक स्थान बाद), और उनका अंतर O(log n) में उपस्थितियों की संख्या देता है। आगे हम उत्तरों के संभावित परास पर होने वाली द्विआधारी search का अध्ययन करेंगे, जहाँ search-क्षेत्र सरणी का सूचकांक नहीं, बल्कि संभावित उत्तरों का परास होता है।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “निचली सीमा और ऊपरी सीमा” पाठ निःशुल्क है?
हाँ—“निचली सीमा और ऊपरी सीमा” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“निचली सीमा और ऊपरी सीमा” में मैं क्या सीखूँगा?
bisect_left और bisect_right को शुरुआत से लागू कीजिए, फिर उनका उपयोग लक्ष्य मान की पहली और अंतिम स्थिति खोजने में कीजिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।
“निचली सीमा और ऊपरी सीमा” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य
- घुमाए गए और अव्यवस्थित ऐरे में द्विआधारी खोज
- निचली सीमा और ऊपरी सीमा
- उत्तर-स्थान पर द्विआधारी खोज