ओ (लॉगन)

Question

में मर्ज किए गए सरणी में मध्य तत्व खोजें हमारे पास एक ही आकार के दो क्रमबद्ध सरणी हैं। आइए ए और बी को कॉल करें।

ए और बी द्वारा विलय किए गए क्रमबद्ध सरणी में मध्य तत्व को कैसे ढूंढें?

Example: 

n = 4 
a = [1, 2, 3, 4] 
b = [3, 4, 5, 6] 

merged = [1, 2, 3, 3, 4, 4, 5, 6] 
mid_element = merged[(0 + merged.length - 1)/2] = merged[3] = 3 

अधिक जटिल मामलों:

केस 1:

a = [1, 2, 3, 4] 
b = [3, 4, 5, 6] 

केस 2:

a = [1, 2, 3, 4, 8] 
b = [3, 4, 5, 6, 7] 

केस 3:

a = [1, 2, 3, 4, 8] 
b = [0, 4, 5, 6, 7] 

प्रकरण 4:

a = [1, 3, 5, 7] 
b = [2, 4, 6, 8] 

---

आवश्यक समय: हे (लॉग एन)। कोई विचार?

Answer 1

दोनों सरणी के बीच में देखें। मान लें कि एक मान छोटा है और दूसरा बड़ा है।

छोटे मान के साथ सरणी के निचले हिस्से को छोड़ दें। उच्च मूल्य के साथ सरणी के ऊपरी भाग को छोड़ दें। अब हमने जो कुछ भी शुरू किया है उसके साथ हमें छोड़ दिया गया है।

कुल्ला और दोहराएं जब तक कि प्रत्येक सरणी में केवल एक तत्व नहीं छोड़ा जाता है। उन दोनों के छोटे से लौटें।

यदि दो मध्यम मान समान हैं, तो मनमाने ढंग से चुनें।

क्रेडिट: Bill Li's blog

Answer 2

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

नोट: यदि आपको पहले सरणी में औसत नहीं मिलेगा तो दूसरी सरणी में प्रारंभिक खोज शुरू करें। इससे जटिलता पर प्रभाव नहीं पड़ेगा

Answer 3

तो, एन = 4 और एक = [1, 2, 3, 4] और b = [3, 4, 5, 6]

आप होने एन के आधार पर अग्रिम में परिणाम सरणी में के-वें स्थिति को जानें, जो एन के बराबर है। परिणाम n-th तत्व पहली सरणी या दूसरे में हो सकता है। आइए पहले मान लें कि तत्व पहले सरणी में है तो प्रारंभिक एल = 0, आर = 3 में मध्य तत्व को [एल, आर] से बाइनरी खोज लेते हैं; तो मध्यम तत्व लेते हुए आप जानते हैं कि एक ही सरणी में कितने तत्व छोटे हैं, जो मध्य -1 है। यह जानकर कि मध्य -1 तत्व कम है और आपको पता है कि आपको एन-वें तत्व की आवश्यकता है, आपके पास [n - (middle-1)] तत्व हो सकता है, दूसरे सरणी से वें तत्व छोटे, बड़े हो सकते हैं। यदि यह अधिक है और प्रीवियो तत्व छोटा है तो यह वही है जो आपको चाहिए, यदि यह अधिक है और पिछला भी अधिक है तो हमें एल = मध्य की आवश्यकता है, यदि यह छोटा आर = मध्य है। यदि आपको पहले समाधान नहीं मिला तो दूसरी सरणी के लिए ऐसा ही करें। कुल लॉग में (एन) + लॉग (एन)