जावा में सूची में बाइनरी खोज क्यों करें?

Question

मुझे यकीन नहीं है कि सामान्य डेटा संरचना के रूप में सूची में बाइनरी खोज एल्गोरिदम क्यों होना चाहिए, सूची को सॉर्ट किया गया है। get विधि जो इंडेक्स को अनुक्रमिक रूप से सूची को अनुक्रमित करती है, कम से कम List के उप प्रकार LinkedList के लिए? यदि ऐसा है, तो मुझे LinkedList के अनुक्रमिक तुलना की तुलना में बाइनरी खोज का उपयोग करने का कोई लाभ नहीं दिख रहा है। बेशक जब तक हम सूची को ArrayList तक सीमित नहीं करते हैं, हम अधिक आत्मविश्वास के साथ बाइनरी खोज कर सकते हैं।

क्या मेरी समझ सही है? धन्यवाद।

Answer 1

List को लागू करने के कई तरीके हैं। वहाँ मानक जावा पुस्तकालयों में आदि, ArrayList, LinkedList है CopyOnWriteArrayList, है, और उन से परे अन्य कार्यान्वयन के एक मेजबान (VLists, परिपत्र बफ़र्स, तिरछा द्विपद सूचियों, extendible arrays, 2-3 finger trees, आदि)। द्विआधारी खोज प्रदान करने के पीछे विचार यह है कि जब सभी सूची कार्यान्वयन यादृच्छिक पहुंच का समर्थन नहीं करते हैं, तो जो लोग बाइनरी खोज के सामान्य कार्यान्वयन से लाभ प्राप्त करेंगे, ताकि प्रत्येक डेटा संरचना के लेखकों को इसे खरोंच से पुन: लागू करने की आवश्यकता न हो। उदाहरण के लिए, यदि मैं एक पागल नई सूची संरचना को कार्यान्वित करता हूं जो यादृच्छिक अभिगम का समर्थन करता है, यदि मैं सूची इंटरफ़ेस को कार्यान्वित करता हूं तो मैं संग्रह कक्षा से स्वचालित रूप से एक बाइनरी खोज प्राप्त कर सकता हूं।

दिलचस्प बात यह है binarySearch विधि इस तरह लिखा है कि यह List के प्रकार को देखता है और देखता है कि क्या यह RandomAccess इंटरफ़ेस लागू करता है इससे पहले कि यह वास्तव में द्विआधारी खोज करता है। यदि सूची RandomAccess लागू नहीं करती है, तो मानक बाइनरी खोज का उपयोग करने के बजाय, विधि इटरेटर्स के साथ एक संशोधित बाइनरी खोज का उपयोग करती है जो अधिकांश ओ (एन) पुनरावृत्तियों और ओ (लॉग एन) तुलना करने की गारंटी है। विचार यह है कि आखिरी जांच कहां उतरी है, फिर अगली जांच स्थान आदि को खोजने के लिए उचित संख्या में कदम आगे या पीछे चलने का विचार रखना है। कुल काम तब किया जाता है जब अधिकांश एन/2 + एन/4 + एन/8 + एन/16 + ... = 2 एन, इसलिए सबसे बुरी स्थिति में यह सबसे बुरी स्थिति रैखिक खोज के रूप में केवल दोगुना है।

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

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

आशा है कि इससे मदद मिलती है!

Answer 2

हां, आप सही हैं, अगर कोई सूची यादृच्छिक पहुंच प्रदान नहीं करती है, जो लिंक्डलिस्ट के मामले में है, तो इसका कोई फायदा नहीं है। Collections.binarySearch() की जावाडोक से:

इस विधि लॉग में एक "यादृच्छिक अभिगम" सूची के लिए (एन) समय (जो लगभग निरंतर समय स्थितीय पहुँच प्रदान करता है) चलाता है। यदि निर्दिष्ट सूची {@link RandomAccess} इंटरफ़ेस को लागू नहीं करती है और यह बड़ी है, तो यह विधि एक पुनरावर्तक-आधारित बाइनरी खोज करेगी जो ओ (एन) लिंक ट्रैवर्सल और ओ (लॉग एन) तत्व तुलना करता है।हे (एन) -

इसलिए, इस मामले में जटिलता अनुक्रमिक तुलना के मामले में के रूप में ही किया जाएगा। व्यावहारिक रूप से, मेरा मानना ​​है कि अनुक्रमिक तुलना कई मामलों में तेजी से हो सकती है।