बाइनरी सर्च कैसे काम करती है, और इसके लिए क्या आवश्यक है?

Question

Accepted Answer

**Binary search** एक **सॉर्ट किए हुए** सरणी में लक्ष्य को खोजता है, खोज श्रेणी को बार-बार आधा करके। प्रत्येक तुलना शेष तत्वों के आधे को हटाती है, **O(log n)** समय देती है। ## विचार मध्य तत्व को देखें। यदि यह लक्ष्य के बराबर है, तो हो गया। यदि लक्ष्य छोटा है, तो बाईं ओर खोजें; यदि बड़ा है, तो दाईं ओर खोजें। जब तक न मिल जाए या श्रेणी खाली न हो जाए, तब तक दोहराएं। ## उदाहरण ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## ट्रेस ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## जटिलता - **समय:** O(log n). **स्थान:** O(1) पुनरावर्तनीय। ## नुकसान **इनपुट को सॉर्ट किया जाना चाहिए** — अन्यथा परिणाम अर्थहीन हैं। `lo`/`hi` में ऑफ-बाय-वन बग्स और कुछ भाषाओं में पूर्णांक ओवरफ़्लो पर ध्यान दें (आ `lo + (hi-lo)//2` का उपयोग करें)। ## यह महत्वपूर्ण क्यों है खोज स्थान को आधा करने से दस लाख तत्वों की खोज ~20 तुलनाओं में बदल जाती है। इसके पीछे का विभाजन-और-विजय पैटर्न पेड़ों, डेटाबेस और अनगिनत साक्षात्कार समस्याओं में दोबारा दिखाई देता है। इसकी एक कठोर आवश्यकता को जानना — सॉर्ट किया हुआ इनपुट — एक क्लासिक सूक्ष्म बग से बचाता है।