बाइनरी सर्च एक सर्चिंग एल्गोरिथम है जिसका उपयोग सॉर्ट की गई ऐरे से एलिमेंट सर्च करने के लिए किया जाता है। इसका उपयोग अनसॉर्ट की गई ऐरे से सर्च करने के लिए नहीं किया जा सकता। बाइनरी सर्च एक कुशल एल्गोरिथम है और टाइम कॉम्प्लेक्सिटी के मामले में लीनियर सर्च से बेहतर है।
लीनियर सर्च की टाइम कॉम्प्लेक्सिटी O(n) है। जबकि बाइनरी सर्च की टाइम कॉम्प्लेक्सिटी O(log n) है। इसलिए, बाइनरी सर्च एक कुशल और तेज़ सर्चिंग एल्गोरिथम है लेकिन इसका उपयोग केवल सॉर्ट की गई ऐरे से सर्च करने के लिए किया जा सकता है।
बाइनरी सर्च कैसे काम करता है?
बाइनरी सर्च के पीछे मूल विचार यह है कि आवश्यक एलिमेंट की तुलना ऐरे के सभी एलिमेंट्स के साथ करने के बजाय, हम आवश्यक एलिमेंट की तुलना ऐरे के मध्य एलिमेंट के साथ करेंगे। यदि यह वह एलिमेंट निकलता है जिसे हम ढूंढ रहे हैं, तो हम सर्च सफलतापूर्वक पूरा कर लेते हैं। अन्यथा, यदि हम जिस एलिमेंट को ढूंढ रहे हैं वह मध्य एलिमेंट से कम है, तो यह निश्चित है कि एलिमेंट ऐरे के पहले या बाएं आधे भाग में स्थित है, क्योंकि ऐरे सॉर्ट की गई है। इसी तरह, यदि हम जिस एलिमेंट को ढूंढ रहे हैं वह मध्य एलिमेंट से बड़ा है, तो यह निश्चित है कि एलिमेंट ऐरे के दूसरे आधे भाग में स्थित है।
इस प्रकार, बाइनरी सर्च लगातार ऐरे को आधा कर देती है। उपरोक्त प्रक्रिया चयनित ऐरे के आधे भाग पर रिकर्सिवली लागू की जाती है जब तक हम उस एलिमेंट को नहीं ढूंढ लेते जिसे हम ढूंढ रहे हैं।
हम बाएं इंडेक्स 0 और दाएं इंडेक्स ऐरे के अंतिम इंडेक्स के बराबर के साथ सर्च शुरू करेंगे। मध्य एलिमेंट इंडेक्स (mid) की गणना की जाती है जो बाएं और दाएं इंडेक्स के योग को 2 से विभाजित करने पर प्राप्त होता है। यदि आवश्यक एलिमेंट मध्य एलिमेंट से कम है, तो दायां इंडेक्स mid-1 में बदल जाता है, जिसका अर्थ है कि अब हम केवल ऐरे के पहले आधे भाग को देखेंगे। इसी तरह, यदि आवश्यक एलिमेंट मध्य एलिमेंट से बड़ा है, तो बायां इंडेक्स mid+1 में बदल जाता है, जिसका अर्थ है कि अब हम केवल ऐरे के दूसरे आधे भाग को देखेंगे। हम चयनित ऐरे आधे के लिए उपरोक्त प्रक्रिया दोहराएंगे।
हमें कैसे पता चलेगा कि एलिमेंट ऐरे में मौजूद नहीं है?
हमें सर्च को रोकने के लिए कुछ कंडीशन की आवश्यकता होती है जो इंगित करेगी कि एलिमेंट ऐरे में मौजूद नहीं है। हम ऐरे में एलिमेंट के लिए इटरेटिवली सर्च करेंगे जब तक बायां इंडेक्स दाएं इंडेक्स से कम या बराबर है। एक बार यह कंडीशन फाल्स हो जाती है और हमने अभी तक एलिमेंट नहीं ढूंढा है, तो इसका मतलब है कि एलिमेंट ऐरे में मौजूद नहीं है।
उदाहरण
आइए निम्नलिखित सॉर्ट की गई ऐरे को लें और हमें एलिमेंट 6 सर्च करना है।
| 2 | 5 | 6 | 8 | 10 | 11 | 13 | 15 | 16 |
L=0 H=8 Mid=4
| 2 | 5 | 6 | 8 | 10 | 11 | 13 | 15 | 16 |
6 < 10, इसलिए पहला आधा भाग लें।
H = Mid-1
L=0 H=3 Mid=1
| 2 | 5 | 6 | 8 | 10 | 11 | 13 | 15 | 16 |
6 > 5, इसलिए दूसरा आधा भाग चुनें।
L = Mid+1
L=2 H=3 Mid=2
| 2 | 5 | 6 | 8 | 10 | 11 | 13 | 15 | 16 |
6 == 6, एलिमेंट मिल गया
इस प्रकार एलिमेंट 6 इंडेक्स 2 पर पाया गया।
कार्यान्वयन
एक दी गई सॉर्ट की गई ऐरे से, आवश्यक एलिमेंट को सर्च करें और यदि एलिमेंट ऐरे में मौजूद है तो उसका इंडेक्स प्रिंट करें। यदि एलिमेंट मौजूद नहीं है, तो -1 प्रिंट करें।
बाइनरी सर्च के कार्यान्वयन का कोड नीचे दिया गया है।
उदाहरण
def binary_search(arr, x):
l = 0
r = len(arr) - 1
while l <= r:
mid = (l + r) // 2
if arr[mid] == x:
return mid
elif x < arr[mid]:
r = mid - 1
elif x > arr[mid]:
l = mid + 1
return -1
array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
a = 7
print(binary_search(array, a))
b = 15
print(binary_search(array, b))
आउटपुट
6
-1एलिमेंट 7 इंडेक्स 6 पर मौजूद है।
एलिमेंट 15 ऐरे में मौजूद नहीं है, इसलिए -1 प्रिंट होता है।
