बाइनरी खोज एल्गोरिथ्म क्रमबद्ध एरे मा एक विशेष मान फेला पार्न को लागी एक कुशल विधि हो। यो दृष्टिकोणले एर्रेलाई साना भागहरूमा विभाजन गर्छ र खोज दायराको बीचमा रहेको मानलाई लक्ष्य मानसँग लगातार तुलना गर्छ। यदि मानहरू मेल खान्छ भने, इच्छित मान फेला पर्नेछ; अन्यथा, एल्गोरिथ्मले खोज दायरालाई संकुचित गर्न जारी राख्छ र मान फेला नपरेसम्म वा थप तत्वहरू जाँच गर्न बाँकी नभएसम्म प्रक्रिया दोहोर्याउँछ।
चरणहरू:
- खोज दायरा प्रारम्भ गर्नुहोस्: एरेको
leftअन्तिम स्थितिमा पहिलो स्थानबाट खोज दायरा चयन गरेर सुरु गर्नुहोस् ।right - मध्य बिन्दु पत्ता लगाउनुहोस्: औसत
leftर दायाँ स्थानहरू द्वारा मध्य बिन्दु गणना गर्नुहोस्; यो खोज दायराको मध्य बिन्दु हो। - मानहरू तुलना गर्नुहोस्: मध्य बिन्दुमा रहेको मानलाई लक्ष्य मानसँग तुलना गर्नुहोस्।
- तुलना परिणाम ह्यान्डल गर्नुहोस्: यदि मध्य बिन्दुको मान लक्ष्य मानसँग मेल खान्छ भने, यो स्थिति फर्काउनुहोस्। यदि मध्य बिन्दुको मान लक्ष्य मान भन्दा कम छ भने, दायाँ आधा खोज्नको लागि बायाँ स्थिति मध्य + 1 मा अपडेट गर्नुहोस्। यदि मध्य बिन्दुको मान लक्ष्य मान भन्दा ठूलो छ भने, बायाँ आधा खोज्नको लागि मध्य- 1 मा दायाँ स्थिति अपडेट गर्नुहोस्।
- दोहोर्याउनुहोस्: चरणहरू 2 देखि 4 सम्म दोहोर्याउनुहोस् जबसम्म मान फेला पर्दैन वा त्यहाँ जाँच गर्न थप तत्वहरू छैनन्
left > right।
फाइदा र बेफाइदाहरू
फाइदा:
- कुशल कार्यसम्पादन: एल्गोरिदमको समय जटिलता O(log n) हो, यसले ठूला डाटासेटहरू ह्यान्डल गर्नको लागि अत्यधिक कुशल बनाउँछ।
- ठूला डाटासेटहरूको लागि प्रभावकारी: बाइनरी खोजले ठूला डाटासेटहरूको लागि द्रुत रूपमा जाँच गर्न तत्वहरूको संख्या घटाउन प्रभावकारी हुन्छ।
बेफाइदाहरू:
- क्रमबद्ध एरेहरूमा मात्र लागू हुन्छ: एल्गोरिदमले क्रमबद्ध एरेहरूमा मात्र काम गर्दछ।
- चरणहरूको चर संख्या: मान पत्ता लगाउन आवश्यक चरणहरूको संख्या एरेमा यसको स्थितिमा निर्भर गर्दछ, र यसले छेउको नजिक मानहरूको लागि धेरै चरणहरू लिन सक्छ।
उदाहरण: PHP मा क्रमबद्ध एरेमा मान १२ फेला पार्नको लागि बाइनरी खोज
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 मा फेला पर्यो।"