Programming Pearls (दूसरा संस्करण) कॉलम 5, समस्या 5 प्रश्न एक अनुरक्षित सरणी पर बाइनरी खोज को कार्यान्वित करने के बारे में है।प्रोग्रामिंग मोती समस्या: द्विआधारी खोज में क्रमबद्ध सरणी के लिए जांच
कैसे आप आंशिक जाँच के समारोह में काफी कम हे से जोड़ सकते हैं (n-1) की लागत?
मुझे पता है कि आप प्रत्येक पुनरावृत्ति के साथ जांच कर सकते हैं और ओ (लॉग एन) प्राप्त कर सकते हैं, लेकिन पीठ में संकेत से पता चलता है कि ओ (1) समाधान है।
वह समाधान क्या है?
सारांश
आंशिक रूप से चल सके कि सरणी ताकि द्विआधारी खोज लागू (लॉग एन) ओ में किया जा सकता है, के रूप ओपी कहा है क्रमबद्ध हो जाता है, और ओ में (1)। ओ (लॉग एन) विधि पिछले जांच के खिलाफ प्रत्येक जांच को जांचना है ताकि यह सुनिश्चित किया जा सके कि यह ठीक से तुलना करता है (इससे भी कम, उससे कम)। ओ (1) विधि केवल बाइनरी खोज और उसके बगल में पाए गए अंतिम तत्व को जांचना है ताकि अगर मांग के बाद तत्व नहीं मिला, कम से कम सम्मिलन के लिए सही जगह मिली। यदि मांगा गया तत्व पाया गया था, तो यह एक अच्छा ओ (1) आंशिक जांच है।
लंबे समय तक स्पष्टीकरण
कोड ब्लॉक से पहले समस्या का एक हिस्सा का कहना है कि एक आम समस्या एक अवर्गीकृत सरणी पर द्विआधारी खोज का उपयोग कर रहा है। असल में, आंशिक जांच का उपयोग यह जांचने के लिए कैसे किया जा सकता है कि ओ (एन -1) लागत से कम में कोई सरणी सॉर्ट की गई है या नहीं?
ओ (लॉग एन) समाधान पिछले जांच के संबंध में प्रत्येक बाइनरी खोज जांच मेस को जांचना है (यह अपेक्षा से कम या उससे अधिक है)। यह गारंटी नहीं देता है कि सरणी क्रमबद्ध है, लेकिन यह एक अच्छा आंशिक जांच है।
एकमात्र ओ (1) चेक जो मैं सोच सकता हूं वह है कि खोज की गई अंतिम जगह की जांच करना है जैसे कि उसके मूल्य और पड़ोसी मूल्यों के विचार के साथ जाल जहां तत्व की खोज की जानी चाहिए, भले ही तत्व नहीं मिला था यह एक बहुत अच्छा आंशिक जांच है: यदि तत्व पाया जाता है तो चीजें शायद सही तरीके से काम कर रही हैं। यदि यह नहीं था, तो उसके आस-पास के तत्वों की जांच करें जहां यह होना चाहिए कि तत्व की खोज से कम एक और फिर तत्व की खोज से अधिक है। हालांकि, मुझे एहसास है कि इस तरीके से जांचना मतलब है कि द्विआधारी खोज, जो ओ (लॉग एन) है, पहले से ही किया जा चुका है, इसलिए मुझे नहीं पता कि यह वास्तव में ओ (1) है या नहीं। हालांकि, यह केवल समग्र खोज में ओ (1) जोड़ता है, इसलिए मुझे लगता है कि यह लागू है।
अच्छी तरह से लिखा है। मैं सोच रहा था कि यह समाधान हो सकता है, लेकिन यह मेरे लिए थोड़ा अजीब लग रहा था कि केवल अंतिम परिणाम की जांच करने से आपको यह जांचने देगी कि सरणी को सॉर्ट किया गया था या नहीं। यह वास्तव में क्या करता है यह जांचें कि जब आप पूरा कर लेंगे तो आप सूक्ष्म-मान्य स्थिति में हैं। अपने आप को घाटी में ढूंढना अभी भी संभव होगा जहां स्थानीय तत्वों को क्रमबद्ध किया गया था, लेकिन जिस तत्व को आप खोज रहे हैं वह कहीं और नहीं छोड़ा गया था: [1,2,4,5,6,7,3,10] यदि आप खोजते हैं 3 आपको लगता है कि यह क्रमबद्ध है और नहीं मिलेगा [3] – Hortitude
हाँ, यही कारण है कि इसे आंशिक जांच कहा जाता है। यह गारंटी नहीं देता है कि सरणी क्रमबद्ध है, लेकिन शायद यह है। पूरी तरह से जांचने का एकमात्र तरीका रैखिक तरीका है, लेकिन आंशिक जांच भी अच्छी हो सकती है। –
थोड़ा और विस्तृत? – pavanlimo