बाइनरी सर्च कसरी काम गर्छ, र यसलाई के आवश्यक छ?

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 तुलनामा परिणत गर्छ। यसको पछाडि रहेको divide-and-conquer ढाँचा रूखहरू, डाटाबेसहरू र अनगिनत साक्षात्कार समस्याहरूमा पुनरावृत्ति हुन्छ। यसको एक गहिरो आवश्यकता — क्रमबद्ध इनपुट — जान्नुले तपाईलाई एक उत्कृष्ट सूक्ष्म बग बाट बचाई राख्छ।