किसी अनुक्रमित अनुक्रम में दिए गए पहले नंबर से पहले नंबर प्राप्त करें

Question

सकारात्मक पूर्णांक और एक पूर्णांक एम के अनुक्रम को देखते हुए, अनुक्रम में पहला नंबर लौटाएं जो एम से अधिक है (या -1 यदि यह अस्तित्व में नहीं है) ।

उदाहरण: अनुक्रम = [2, 50, 8, 9, 1], एम = 3 -> वापसी = 50

हे (लॉग एन) प्रत्येक प्रश्न के लिए आवश्यक (preprocessing के बाद) के लिए।

मैं BSTs के बारे में सोचा है, लेकिन एक आरोही अनुक्रम मैं सिर्फ एक लंबे पथ प्राप्त होता है, जो मुझे ओ (logn) समय देना नहीं होता ...

संपादित दिया: प्रयुक्त संरचना भी होना चाहिए संशोधित करने में आसान, यानी उस तत्व के साथ पाए गए तत्व को प्रतिस्थापित करना संभव है और किसी अन्य एम के लिए खोज दोहराएं (सबकुछ - प्रीप्रोकैसिंग - ओ (लॉगन) के अलावा)। और निश्चित रूप से यह अच्छा होगा, अगर मैं 'पहले बड़े' को 'पहले छोटे' में बदल सकता हूं और एल्गोरिदम में बहुत अधिक परिवर्तन नहीं करना पड़ता था। और यदि यह मदद करता है, तो हम मान सकते हैं कि सभी संख्याएं सकारात्मक हैं और कोई दोहराव नहीं है।

Answer 1

एक दूसरी सरणी बनाएँ (रहने दो aux) प्रत्येक तत्व i के लिए जहां: aux[i] = max { arr[0],arr[1], ... ,arr[i]} (मूल सरणी में सूचकांक j <= i साथ सभी तत्वों की अधिकतम)।

यह देखना आसान है कि यह सरणी प्रकृति द्वारा क्रमबद्ध है, और aux पर एक साधारण binary search आवश्यक सूचकांक प्राप्त करेगा। (बाइनरी खोज के साथ प्राप्त करना आसान है जो पहले तत्व से अधिक है तो अनुरोध तत्व यदि तत्व मौजूद नहीं है)।

समय जटिलता O(n) प्री-प्रोसेसिंग (केवल एक बार किया गया) और O(logn) प्रति क्वेरी है।