इस समस्या में हमें अनंत सॉर्टेड संख्याओं से युक्त एक सरणी दी गई है। हमारा कार्य अनंत संख्याओं की सॉर्टेड सरणी में एक तत्व की स्थिति खोजना है।
आइए एक उदाहरण से इस समस्या को समझते हैं,
इनपुट
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