बाइनरी सर्च एक ऐसा तरीका है जिससे क्रमबद्ध सरणी में आवश्यक तत्व को बार-बार आधा करके और आधे में खोज कर खोजा जा सकता है।
यह विधि संपूर्ण सरणी से प्रारंभ करके की जाती है। फिर इसे आधा कर दिया जाता है। यदि आवश्यक डेटा मान सरणी के मध्य में तत्व से अधिक है, तो सरणी के ऊपरी आधे हिस्से पर विचार किया जाता है। अन्यथा, निचला आधा माना जाता है। यह तब तक लगातार किया जाता है जब तक या तो आवश्यक डेटा मान प्राप्त नहीं हो जाता या शेष सरणी खाली नहीं हो जाती।
C++ में बाइनरी सर्च को प्रदर्शित करने वाला प्रोग्राम नीचे दिया गया है।
उदाहरण
#include
using namespace std;
int binarySearch(int arr[], int p, int r, int num) {
if (p <= r) {
int mid = (p + r)/2;
if (arr[mid] == num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num);
if (arr[mid] < num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
}
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int num;
cout << "Enter the number to search: \n";
cin >> num;
int index = binarySearch (arr, 0, n-1, num);
if(index == -1){
cout<< num <<" is not present in the array";
}else{
cout<< num <<" is present at index "<< index <<" in the array";
}
return 0;
} आउटपुट
Enter the numberto search 20 20 is present at index 5 in the array
उपरोक्त कार्यक्रम में, बाइनरीसर्च () एक पुनरावर्ती फ़ंक्शन है जिसका उपयोग बाइनरी खोज का उपयोग करके सरणी में आवश्यक तत्व को खोजने के लिए किया जाता है। फ़ंक्शन सरणी, इसकी निचली बाउंड और ऊपरी बाउंड के साथ-साथ पैरामीटर के रूप में पाई जाने वाली संख्या लेता है। यह नीचे दिखाया गया है।
int binarySearch(int arr[], int p, int r, int num)
फिर सरणी के मध्य बिंदु की गणना की जाती है। यदि मध्य बिंदु पर मान संख्या के बराबर है, तो इसे वापस कर दिया जाता है। यदि मान संख्या से अधिक है, तो सरणी निचले बाउंड पी और ऊपरी बाउंड मध्य -1 के साथ पुनरावर्ती रूप से कॉल करती है। यदि मान संख्या से कम है, तो सरणी निम्न बाउंड मध्य + 1 और ऊपरी बाउंड r के साथ स्वयं को पुनरावर्ती रूप से कॉल करती है। इसे निम्नलिखित कोड स्निपेट द्वारा देखा जा सकता है।
int binarySearch(int arr[], int p, int r, int num) {
if (p <= r) {
int mid = (p + r)/2;
if (arr[mid] == num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num);
if (arr[mid] < num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
} मुख्य () फ़ंक्शन में, सरणी गिरफ्तारी [] परिभाषित की गई है। सरणी के आकार की गणना की जाती है और पाई जाने वाली संख्या निर्दिष्ट की जाती है। फिर बाइनरीसर्च () को संख्या के सूचकांक को खोजने के लिए कहा जाता है। यदि बाइनरीसर्च () द्वारा लौटाया गया मान -1 है, तो संख्या सरणी में नहीं है। अन्यथा, सूचकांक मूल्य वापस कर दिया जाता है। यह नीचे दिया गया है।
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int num = 33;
int index = binarySearch (arr, 0, n-1, num);
if(index == -1)
cout<< num <<" is not present in the array";
else
cout<< num <<" is present at index "<< index <<" in the array";
return 0;
}