बाइनरी सर्च
क्रमबद्ध ऐरे में तत्व खोजने की कुशल विधि। ऐरे को बार-बार आधा करके खोज अंतराल कम किया जाता है। समय जटिलता: O(log n)।
एल्गोरिदम
- पूरे ऐरे से शुरू करें
- मध्य तत्व जांचें
- यदि लक्ष्य मध्य से बड़ा: ऊपरी आधा खोजें
- यदि लक्ष्य मध्य से छोटा: निचला आधा खोजें
- दोहराएं जब तक मिल न जाए या ऐरे खाली न हो जाए
C++ प्रोग्राम उदाहरण (रिकर्सिव)
#include <iostream>
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);
return binarySearch(arr, mid + 1, r, num);
}
return -1;
}
int main() {
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: ";
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 number to search: 20 20 is present at index 5 in the array
कोड व्याख्या
binarySearch() फ़ंक्शन
रिकर्सिव फ़ंक्शन जो ऐरे, निचली सीमा (p), ऊपरी सीमा (r), और खोज संख्या (num) लेता है। मध्य सूचकांक की गणना करता है और तुलना के आधार पर रिकर्सिव कॉल करता है।
मुख्य फ़ंक्शन
क्रमबद्ध ऐरे परिभाषित करता है, उपयोगकर्ता से खोज संख्या लेता है, बाइनरी सर्च कॉल करता है, और परिणाम प्रदर्शित करता है।
पुनरावृत्तिक (Iterative) संस्करण
int binarySearchIterative(int arr[], int n, int num) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == num) return mid;
if (arr[mid] < num) left = mid + 1;
else right = mid - 1;
}
return -1;
}
आवश्यक शर्त
ऐरे क्रमबद्ध होना चाहिए। अक्रमबद्ध ऐरे पर बाइनरी सर्च काम नहीं करता।