मुझे यकीन है कि वह क्या मन में था नहीं हूँ।
यदि आप सिर्फ एक बार नंबर खोजना चाहते हैं, और आपको कोई गारंटी नहीं है कि सरणी सॉर्ट की गई है, तो मुझे नहीं लगता कि आप रैखिक खोज को हरा सकते हैं। औसतन आपको मूल्य खोजने से पहले सरणी के माध्यम से आधे रास्ते की तलाश करनी होगी, यानी अपेक्षित चलने का समय ओ (एन); सॉर्ट करते समय आपको कम से कम एक बार और प्रत्येक से अधिक मूल्य को छूना पड़ता है, यानी अपेक्षित चलने का समय ओ (एन लॉग एन)।
लेकिन यदि आपको कई मानों को खोजने की आवश्यकता है तो सॉर्ट करने में बिताए गए समय को जल्दी से भुगतान करना पड़ता है। एक क्रमबद्ध सरणी के साथ, आप ओ (लॉग एन) समय में बाइनरी खोज कर सकते हैं, इसलिए यदि आप सॉर्ट करने के लिए समय निवेश करते हैं तो तीसरी खोज से निश्चित रूप से आगे बढ़ें।
यदि आप समस्या से निपटने के लिए अलग-अलग डेटा संरचनाओं को बनाने की अनुमति देते हैं तो आप और भी बेहतर कर सकते हैं। आप किसी प्रकार की अनुक्रमणिका बना सकते हैं, जैसे हैश टेबल; लेकिन इस तरह की समस्या के लिए चैंपियन डेटा संरचना शायद कुछ प्रकार की वृक्ष संरचना होगी। फिर आप पेड़ में नए मानों को तेज़ी से जोड़ सकते हैं, ताकि आप नए मान जोड़ सकें और सरणी को फिर से क्रमबद्ध कर सकें, और लुकअप अभी भी कोई मान खोजने के लिए ओ (लॉग एन) होने जा रहा है। पेड़ के विभिन्न प्रकार उपलब्ध हैं: बाइनरी पेड़, बी-पेड़, ट्राई, आदि
लेकिन जैसा कि @ हॉट लिक्स ने कहा, इस प्रकार की चीज़ के लिए अक्सर हैश टेबल का उपयोग किया जाता है, और यह अद्यतन करने के लिए बहुत सस्ता है: आप केवल मुख्य सरणी पर एक मान संलग्न करें, और नए मान को इंगित करने के लिए हैश तालिका अद्यतन करें। और एक हैश टेबल ओ (1) समय के बहुत करीब है, जिसे आप हरा नहीं सकते। (एक हैश टेबल ओ (1) यदि कोई हैश टकराव नहीं है; एक अच्छा हैश एल्गोरिदम मानना और एक बड़ी पर्याप्त हैश तालिका में लगभग कोई टकराव नहीं होगा। मुझे लगता है कि आप कह सकते हैं कि हैश तालिका ओ (एन) है जहां एन प्रति "बाल्टी" की हैश टकराव की औसत संख्या है। अगर मैं इसके बारे में गलत हूं तो मुझे बहुत जल्दी सुधारने की उम्मीद है; यह स्टैक ओवरफ्लो है!)
आम तौर पर, चीजों के एक बड़े सेट को खोजने के लिए, कोई किसी प्रकार की हैश तालिका का उपयोग करता है। –
[जो तेज है, हैश लुकअप या बाइनरी खोज?] (Http://stackoverflow.com/questions/360040/which-is-faster-hash-lookup-or-binary-search) – Josh
@ जोश - ट्रिक प्रश्न। यदि सबकुछ अच्छी तरह से हल किया गया है और आप कभी भी खोज के लिए सेट को संशोधित नहीं करेंगे, तो द्विआधारी खोज तेज है। लेकिन यह वास्तविक जीवन नहीं है। वास्तविक जीवन में हैश टेबल लगभग हमेशा जीतता है। –