Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में अनंत संख्याओं की सॉर्टेड सरणी में तत्व की स्थिति खोजें


इस समस्या में हमें अनंत सॉर्टेड संख्याओं से युक्त एक सरणी दी गई है। हमारा कार्य अनंत संख्याओं की सॉर्टेड सरणी में एक तत्व की स्थिति खोजना है।

आइए एक उदाहरण से इस समस्या को समझते हैं,

इनपुट

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

  1. - C++ प्रोग्राम: सरणी में प्रत्येक तत्व के लिए निकटतम बड़ा मान ज्ञात करना

    यहां हम देखेंगे कि सरणी में प्रत्येक तत्व के लिए निकटतम मान कैसे ज्ञात करें। यदि किसी तत्व x का अगला तत्व जो उससे बड़ा है, और सरणी में भी मौजूद है, तो वह उस तत्व का बड़ा मान होगा। यदि तत्व मौजूद नहीं है, तो -1 लौटाएं। मान लें सरणी तत्व [10, 5, 11, 6, 20, 12] हैं, तो बड़े तत्व [11, 6, 12, 10, -1, 20]

  1. - C++ में रोटेटेड सॉर्टेड सरणी में रोटेशन काउंट ढूंढना

    मान लीजिए हमारे पास एक सरणी है, जो रोटेटेड सॉर्टेड सरणी है। हमें उन रोटेशन की संख्या ढूंढनी है जो सरणी को सॉर्ट करने के लिए आवश्यक हैं। (हम रोटेशन दाएं से बाएं मानेंगे।)मान लीजिए सरणी ऐसी है: {15, 17, 1, 2, 6, 11}, तो हमें सरणी को दो बार रोटेट करना होगा ताकि यह सॉर्ट हो जाए। अंतिम क्रम {1, 2, 6, 11,

  1. - C++ में सरणी के प्रत्येक तत्व का सरपासर काउंट खोजें

    मान लीजिए एक सरणी A दी गई है। हमें उस सरणी में प्रत्येक तत्व के सरपासर की संख्या ज्ञात करनी है। सरपासर वे बड़े तत्व हैं जो वर्तमान तत्व के दाईं ओर सरणी में मौजूद हैं। मान लीजिए A = {2, 7, 5, 3, 0, 8, 1}, सरपासर हैं {4, 1, 1, 1, 2, 0, 0}, इसलिए 2 के दाईं ओर 4 संख्याएं हैं जो 2 से बड़ी हैं, और इसी नि