एक सरणी दी जाती है जैसे कि उसके तत्व का मान 0 (के -1) के माध्यम से 0 वें इंडेक्स से बढ़ता है। के पर मान न्यूनतम है, और यह n वें तत्व के माध्यम से फिर से बढ़ना शुरू हो जाता है। न्यूनतम तत्व खोजें।एक सरणी में कम से कम तत्व खोजें, जिसमें एक पैटर्न
अनिवार्य रूप से, इसकी एक क्रमबद्ध सूची किसी अन्य में संलग्न होती है; उदाहरण: (1, 2, 3, 4, , 1, 2, 3)।
मैंने सभी प्रकार के एल्गोरिदम की कोशिश की है जैसे बल्बिंग मिनी-हीप, त्वरित चयन या केवल सादा ट्रैवर्सिंग। लेकिन इसे ओ (एन) से नीचे नहीं मिल सकता है। लेकिन इस सरणी में एक पैटर्न है, जो कुछ बाइनरी खोज प्रकार की चीज का सुझाव देना संभव है, और जटिलता ओ (लॉग एन) जैसी कुछ होनी चाहिए, लेकिन कुछ भी नहीं मिल सकता है। विचार ??
धन्यवाद
क्या आपका मतलब है ** ** 0 से 0 तक घटता है? –
नहीं, यह के से कम से कम किसी भी मूल्य से कम हो सकता है, फिर से कम हो सकता है और फिर फिर से बढ़ना शुरू हो जाता है। इसकी तरह हमने एक सूची में एक के बाद दो क्रमबद्ध सरणी रखी है और हमें विलय बिंदु खोजने की जरूरत है। –
मैंने विचार को स्पष्ट रूप से स्पष्ट करने के लिए प्रश्न संपादित किया है, क्योंकि मैंने गलत समझा (और स्पष्ट रूप से केवल एक ही नहीं था)। @ जिम मिशेल स्पष्ट स्पष्टीकरण के लिए क्रेडिट प्राप्त करता है। – derobert