बाइनरी सर्च एल्गोरिदम एक क्रमबद्ध सरणी में एक विशिष्ट मान खोजने के लिए एक कुशल तरीका है। यह दृष्टिकोण सरणी को छोटे भागों में विभाजित करता है और लक्ष्य मान के साथ खोज सीमा के मध्य स्थान पर मान की लगातार तुलना करता है। यदि मान मेल खाते हैं, तो वांछित मान मिल जाता है; अन्यथा, एल्गोरिदम खोज सीमा को कम करना जारी रखता है और प्रक्रिया को तब तक दोहराता है जब तक कि मूल्य नहीं मिल जाता है या जांच के लिए कोई और तत्व नहीं बचा है।
कदम:
- खोज श्रेणी प्रारंभ करें: सरणी की पहली स्थिति से
leftअंतिम स्थिति तक खोज श्रेणी का चयन करके प्रारंभ करें।right - मध्य बिंदु खोजें:
leftऔसत और सही स्थितियों के आधार पर मध्य बिंदु की गणना करें ; यह खोज सीमा का मध्य बिंदु है. - मूल्यों की तुलना करें: मध्य बिंदु पर मूल्य की तुलना लक्ष्य मूल्य से करें।
- तुलना परिणाम संभालें: यदि मध्य बिंदु पर मान लक्ष्य मान से मेल खाता है, तो इस स्थिति को वापस कर दें। यदि मध्य बिंदु पर मान लक्ष्य मान से कम है, तो दाएँ आधे को खोजने के लिए बाईं स्थिति को मध्य + 1 पर अपडेट करें। यदि मध्य बिंदु पर मान लक्ष्य मान से अधिक है, तो बाएं आधे भाग को खोजने के लिए दाहिनी स्थिति को मध्य- 1 में अपडेट करें।
- दोहराएँ: चरण 2 से 4 तब तक दोहराएँ जब तक कि मान न मिल जाए या जाँचने के लिए कोई और तत्व न रह जाएँ
left > right।
फायदे और नुकसान
लाभ:
- कुशल प्रदर्शन: एल्गोरिदम की समय जटिलता O(लॉग एन) है, जो इसे बड़े डेटासेट को संभालने के लिए अत्यधिक कुशल बनाती है।
- बड़े डेटासेट के लिए प्रभावी: बाइनरी खोज बड़े डेटासेट के लिए शीघ्रता से जांच करने के लिए तत्वों की संख्या को कम करने में प्रभावी है।
नुकसान:
- केवल क्रमबद्ध सरणियों पर लागू: एल्गोरिदम केवल क्रमबद्ध सरणियों पर काम करता है।
- चरणों की परिवर्तनीय संख्या: मान खोजने के लिए आवश्यक चरणों की संख्या सरणी में इसकी स्थिति पर निर्भर करती है, और यह सिरों के निकट मानों के लिए कई कदम उठा सकती है।
उदाहरण: PHP में क्रमबद्ध सरणी में मान 12 खोजने के लिए बाइनरी खोज
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr)- 1;
while($left <= $right) {
$mid = floor(($left + $right) / 2);
if($arr[$mid] == $target) {
return $mid; // Return the position of the value
} elseif($arr[$mid] < $target) {
$left = $mid + 1;
} else {
$right = $mid- 1;
}
}
return -1; // Value not found
}
$array = [2, 5, 8, 12, 15, 20, 30];
$targetValue = 12;
$result = binarySearch($array, $targetValue);
if($result != -1) {
echo "Value $targetValue found at position $result.";
} else {
echo "Value $targetValue not found in the array.";
}
उदाहरण की व्याख्या
- हम सरणी की पहली स्थिति से
left = 0अंतिम स्थिति तक प्रारंभिक खोज सीमा से शुरू करते हैं।right = 6 - हम बाएँ और दाएँ स्थिति के औसत से मध्य बिंदु(मध्य) की गणना करते हैं;
mid = 3. मध्य का मान 12 है। -
mid(12हम लक्ष्य मान(12) के साथ) के मान की तुलना करते हैं और एक मिलान पाते हैं, इसलिए हम स्थिति 3 पर लौटते हैं। - एल्गोरिथ्म समाप्त होता है, और हम परिणाम आउटपुट करते हैं "मान 12 स्थिति 3 पर पाया गया।"