सी # सूची <T>। मूल्य खोज नहीं होने पर BinarySearch वापसी मूल्य

Question

जब आइटम मौजूद नहीं है तो मैं List<T> की बाइनरी खोज विधि के बारे में उलझन में हूं।

मैं अपेक्षा के अनुरूप,

List<long> theList = {1, 3, 5, ...}. 

theList.BInarySearch(0) रिटर्न 0, और theList.BInarySearch(3) रिटर्न 1 मिल गया है।

हालांकि, theList.BinarySearch(1)-2, और -1 जैसा मैं अपेक्षा करता हूं। एमएसडीएन मैनुअल का कहना है: "रिटर्न वैल्यू: सॉर्टेड सूची में आइटम की शून्य-आधारित इंडेक्स, यदि आइटम पाई जाती है, अन्यथा, ऋणात्मक संख्या जो आइटम के मुकाबले अगले तत्व की अनुक्रमणिका का बिटवाई पूरक है या , यदि कोई बड़ा तत्व नहीं है, तो गणना के बिटवाई पूरक। "

एक "bitwise पूरक"? मैं यहाँ क्या खो रहा हूं और यह क्यों है theList.BinarySearch(1) != -1?

Answer 1

पहले - आप -1 क्यों उम्मीद करेंगे? यदि आइटम पहला आइटम है, तो यह -0 (पूर्णांक के लिए) नहीं लौटा सकता है, इसलिए यह कारण 2 है कि दूसरे आइटम के लिए वापस किया जाएगा।

अगला, आप आसानी से ~-2 का उपयोग करके सही सूचकांक प्राप्त कर सकते हैं - bitwise नहीं ऑपरेटर।

Answer 2

एक सम्मिलन बिंदु को बदलने के लिए, बिटवाइज़ पूरक ले, वह यह है कि: ~retval

Answer 3

मुझे लगता है कि आप theList.BinarySearch(2) के बारे में बात कर रहे हैं, क्योंकि 1 मौजूद है और वापसी मान 0 होना चाहिए।

bitwise complement operator पूर्णांक को अस्वीकार करने के समान प्रभाव उत्पन्न नहीं करता है, जो मुझे लगता है कि आपके भ्रम का स्रोत है। किसी भी मामले में, आपको यह समझने की आवश्यकता नहीं है कि ऑपरेटर खोज-परिणाम पर सटीक रूप से शाखा कैसे काम करता है;

int index = theList.BinarySearch(num); 

if (index >= 0) 
{ 
    //exists 
    ... 
} 
else 
{ 
    // doesn't exist 
    int indexOfBiggerNeighbour = ~index; //bitwise complement of the return value 

    if (indexOfBiggerNeighbour == theList.Count) 
    { 
     // bigger than all elements 
     ... 
    } 

    else if (indexOfBiggerNeighbour == 0) 
    { 
     // smaller than all elements 
     ... 
    } 

    else 
    { 
     // Between 2 elements 
     int indexOfSmallerNeighbour = indexOfBiggerNeighbour - 1; 
     ... 
    } 
} 

Answer 4

इन नकारात्मक सूचकांक लौटने के लिए कारण आइटम है कि सूची में नहीं पाए जाते हैं डालने का समर्थन है: अपने प्रश्न में MSDN पैरा, और तथ्य यह है कि ~~a = a, सीधे इस स्निपेट निकलता है। इस उदाहरण में, 2 सूचकांक = 2 ​​पर डाला जाएगा। अन्यथा, आपको उस स्थिति को खोजने के लिए एक और बाइनरी खोज करना होगा।