सूची के लिए BinarySearch का उपयोग कैसे करें <T>

Question

की सूची BinarySearch के इस अधिभार साथ शुरू करते हैं:

public int BinarySearch(T item, IComparer<T> comparer); 

यह सर्वविदित है कि सूची BinarySearch उपयोग करने से पहले उचित IComparer साथ हल कर दिया जाना चाहिए। लेकिन फिर: सूची को खोजने के लिए आपको एक टी आइटम प्रदान करना होगा। यह अपेक्षाकृत अप्रत्याशित है जब किसी को इन वस्तुओं के गुणों (यानी लिंक या प्रतिनिधियों/भविष्यवाणियों का उपयोग करके) सूची में वस्तुओं को खोजने के लिए उपयोग किया जाता है। क्योंकि जब मेरे पास पहले से ही मेरा टी आइटम है तो मुझे इसे खोजना नहीं है!

अब मैं सी #+ कोड को सी # में कार्यान्वित कर रहा था और देखा कि सी ++ प्रोग्रामर ने सी ++ स्टाइल बाइनरी का इस्तेमाल अपने कोड में हर जगह किया है। सबसे पहले उसने एक नया टी आइटम बनाया और इस टी आइटम को वह गुण दिया जो वह ढूंढ रहा था। फिर उन्होंने को उसी गुण के साथ सूची में किसी आइटम की अनुक्रमणिका खोजने के लिए, इसके साथ सूची की खोज की। पाठ्यक्रम की सी ++ तुलनाकर्ता इन गुणों के लिए अनुकूलित किया गया था।

तो यह सूची में आइटम देखने के लिए एक अलग तरीका है। बाइनरीशर्च डमी टी आइटम और एक इंडेक्स की खोज करता है जिसके साथ यह सूची में वास्तविक टी आइटम पुनर्प्राप्त कर सकता है। एक लिंक बिंदु से यह अप्राकृतिक लगता है।

मेरे प्रश्न हैं:

मैं BinarySearch के पीछे विचार का सही विवरण दिया है?

क्या आपको लगता है कि एक डमी टी आइटम पहले बिना बाइनरीशर्च के साथ लिंक शैली खोज का उपयोग करना संभव है?

Answer 1

Did I give a correct description of the idea behind BinarySearch?
हां।

Do you think it is possible to use a Linq style search with BinarySearch without making a dummy T item first?
इसके वर्तमान स्वरूप में नहीं है। आप एक रैपर का उपयोग कर सकते हैं जो आपके लिए डमी टी बनाएगा, यह केवल विशिष्ट त्स के लिए काम करेगा, हालांकि (पैरामीटर रहित कन्स्ट्रक्टर आदि के साथ)।

Answer 2

दरअसल, LINQ में कुछ भी समान नहीं है, लेकिन आप अपने स्वयं के एक्सटेंशन बना सकते हैं। यह उदाहरण आपको नहीं एक डमी आइटम पारित करने के लिए अनुमति देते हैं, लेकिन उदाहरण के लिए सिर्फ मूल comparer में इस्तेमाल किया संपत्ति:

public static int FindFirstIndexGreaterThanOrEqualTo<TElement, TKey>(
       this IList<TElement> keySortedCollection, 
       TKey key, 
       Func<TElement, TKey> keySelector, 
       IComparer<TKey> keyComparer) 
{ 
    int begin = 0; 
    int end = keySortedCollection.Count; 
    while (end > begin) 
    { 
     int index = (begin + end)/2; 
     TElement el = keySortedCollection[index]; 
     TKey currElKey = keySelector(el); 
     if (keyComparer.Compare(currElKey, key) >= 0) 
      end = index; 
     else 
      begin = index + 1; 
    } 
    return end; 
} 

public static int FindFirstIndexGreaterThanOrEqualTo<TElement, TKey>(
       this IList<TElement> keySortedCollection, 
       TKey key, 
       Func<TElement, TKey> keySelector) 
{ 
    return FindFirstIndexGreaterThanOrEqualTo(keySortedCollection, 
               key, 
               keySelector, 
               Comparer<TKey>.Default); 
} 

इन तरीकों के साथ

, आप एक तुलना एक के एक सबसेट आप मूल रूप से प्रयोग किया जाता है कि दे सकता है संग्रह को सॉर्ट करने के लिए।

जाहिर है, जब आप मूल तुलनाकर्ता के उप-समूह का उपयोग कर रहे हैं, तो आप एक एकल अनुक्रमणिका नहीं ढूंढ सकते हैं। तो ये विधियां बाइनरी खोज के निचले स्तर पर लौटती हैं।