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