इस समस्या में हमें अनंत क्रमबद्ध संख्याओं से युक्त एक सरणी दी जाती है। हमारा कार्य अनंत संख्याओं के क्रमबद्ध सरणी में किसी तत्व की स्थिति का पता लगाना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {2, 4, 6, 8, 9, 12, 14,17, ….}, ele = 9 आउटपुट
4
स्पष्टीकरण
समाधान दृष्टिकोण
क्रमबद्ध सरणी से तत्वों को कुशलतापूर्वक खोजने के लिए, हम बाइनरी खोज पद्धति का उपयोग करेंगे। यहां, एकल अंतिम बिंदु ज्ञात नहीं है, हम एल्गोरिथम को थोड़ा संशोधित करेंगे।
हम प्रारंभ सूचक को पहले स्थान पर ठीक करेंगे, फिर अंत सूचक को दूसरी स्थिति में ले जाएंगे। इसके बाद, हम अंत सूचक पर मान की जांच करेंगे और यदि मान कुंजी से कम है तो इसे दोगुना करके बढ़ाएंगे और अंत सूचक की अंतिम स्थिति के साथ प्रारंभ सूचक को अपडेट करेंगे।
जब अंतिम स्थिति मान पाए जाने वाले तत्व से अधिक होता है, तो हम बाइनरी खोज का उपयोग करके इस उप-सरणी में खोज करेंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include<iostream>
using namespace std;
int binarySearch(int arr[], int start, int end, int ele) {
if (end >= start) {
int mid = start + (end - start)/2;
if (arr[mid] == ele)
return mid;
if (arr[mid] > ele)
return binarySearch(arr, start, mid-1, ele);
return binarySearch(arr, mid+1, end, ele);
}
return -1;
}
int findPos(int arr[], int value) {
int start = 0, end = 1;
while (arr[end] < value) {
start = end;
end = 2*end;
}
return binarySearch(arr, start, end, value);
}
int main(){
int arr[] = {1, 2, 4, 6, 8, 9, 12, 14, 17, 21, 45};
int index = findPos(arr, 9);
if (index == -1)
cout<<"Element not found!";
else
cout<<"Element found! index = "<<index;
return 0;
} आउटपुट
Element found! index = 5