अनुक्रमिक रूप से बढ़ने में एक संख्या ढूँढना और उसके बाद अनुक्रमकरा

Question

अनुक्रम में अधिकतम या न्यूनतम मान ढूँढना जो मोन्टोनिक रूप से बढ़ता है और फिर ओनोटोनिक रूप से कम हो जाता है ओ (लॉग एन) में किया जा सकता है।

हालांकि, अगर मैं जांचना चाहता हूं कि इस तरह के अनुक्रम में कोई संख्या मौजूद है, तो क्या यह ओ (लॉग एन) में भी किया जा सकता है?

मुझे नहीं लगता कि यह संभव है। इस उदाहरण पर विचार करें: 1 4 5 6 7 10 8 3 2 0.

इस उदाहरण में, अगर मुझे यह पता लगाना है कि अनुक्रम में '2' है, तो मेरे पास खोज स्थान को आधा में विभाजित करने की कोई शर्त नहीं है मूल खोज स्थान। सबसे बुरी स्थिति में, यह ओ (एन) होगा, क्योंकि आपको दोनों हिस्सों की जांच करने की आवश्यकता है, जब हम 2 की खोज करने की कोशिश कर रहे हैं।

मैं जानना चाहता हूं, अगर यह खोज ओ में किया जाए (लॉग एन) समय?

Answer 1

जैसा कि आपने देखा है, आप ओ (लॉग इन) में अधिकतम (और इसकी स्थिति) पा सकते हैं। फिर आप प्रत्येक भाग में एक बाइनरी खोज कर सकते हैं जो ओ (लॉगऑन) भी है।

उपरोक्त उदाहरण में, आपको स्थिति 5 पर अधिकतम 10 मिलते हैं। फिर आप बाद में [0..5] (1, 4, 5, 6, 7, 10) में बाइनरी खोज करते हैं। जैसा कि 2 नहीं मिला है, आप दूसरे भाग में बाइनरी खोज करने के लिए आगे बढ़ते हैं (10, 8, 3, 2, 0)।

ओ (लॉगन) में अधिकतम खोजने के लिए: केंद्र में दो तत्वों को देखें: 7 < 10. तो हम अभी भी बढ़ते हिस्से में हैं और अनुक्रम के दाहिने हिस्से में अधिकतम को देखना है: (10, 8, 3, 2, 0)। 8 और 3 को बाएं भाग (10, 8) के साथ आगे बढ़ें।

Answer 2

जैसा कि मुझे उन सरणीओं के लिए सबसे अच्छी खोज याद है, जिन्हें तत्वों को बढ़ने का आदेश दिया गया है और फिर घटना फाइबोनैकी खोज एल्गोरिदम है।

Answer 3

यहां पाइथन में एक स्केच है। संक्षेप में हम एक ऐसे तत्व को ढूंढने का लक्ष्य रखते हैं जो बढ़ते और घटते क्षेत्रों से सीमाबद्ध हो (यह हम पड़ोसी तत्वों की जांच करने में दो स्थितियों की जांच करते हैं)। और जब तक हम इस तत्व को नहीं पाते हैं तब तक हम मानक द्विआधारी खोज में छिपते रहते हैं। उम्मीद है की वो मदद करदे।

def get_max(arr): 
    if len(arr) == 1: 
     return arr[0] 
    if len(arr) in [0,2]: 
     return None 
    left, right = 0, len(arr) - 1 
    while left <= right: 
     mid = (left+right) // 2 
     #increasing region 
     if arr[mid+1] > arr[mid] and arr[mid] > arr[mid-1]: 
      left = mid + 1 
     #decreasing region 
     elif arr[mid+1] < arr[mid] and arr[mid] < arr[mid-1]: 
      right = mid - 1 
     elif arr[mid+1] < arr[mid] and arr[mid-1] > arr[mid]: 
      return arr[mid-1] 
     else: 
      return arr[mid] 
    return -1