बायनरी सर्च कसे कार्य करते आणि त्यास काय आवश्यक आहे?

Question

Accepted Answer

**बायनरी सर्च** **क्रमवारीकृत** अरेमध्ये शोध श्रेणी वारंवार अर्धे करून लक्ष्य शोधतो. प्रत्येक तुलना उर्वरित घटकांचा अर्धा भाग काढून टाकते, **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` मध्ये off-by-one बग्स आणि काही भाषांमध्ये पूर्णांक ओव्हरफ्लो साठी सावधान रहा (`lo + (hi-lo)//2` वापरा). ## हे महत्वाचे का आहे शोध स्पेस अर्धे करणे दशलक्ष-घटक लुकअपला अंदाजे 20 तुलनामध्ये बदलते. त्याच्या मागे असलेले विभाजन-आणि-जयत नमुना पुन्हा ट्री, डेटाबेस आणि असंख्य साक्षात्कार समस्यांमध्ये दिसतो. त्याच्या एक कठोर आवश्यकता — क्रमवारीकृत इनपुट — जाणून घेणे आपल्याला एक उत्कृष्ट सूक्ष्म बग पासून रक्षा करते.