गिना जा रहा है मध्य

Question

मैं एक एल्गोरिदम पुस्तक जो द्विआधारी खोज के लिए निम्नलिखित कलन विधि था पढ़ रहा था:

public class BinSearch { 
    static int search (int [ ] A, int K) { 
    int l = 0 ; 
    int u = A. length −1; 
    int m; 
    while (l <= u) { 
     m = (l+u) /2; 
     if (A[m] < K) { 
     l = m + 1 ; 
     } else if (A[m] == K) { 
     return m; 
     } else { 
      u = m−1; 
     } 
     } 
     return −1; 
     } 
} 

लेखक कहते हैं, "त्रुटि काम m = (l+u)/2; में है यह अतिप्रवाह को जन्म दे सकता है और प्रतिस्थापित किया जाना चाहिए m = l + (u-l)/2 द्वारा। "

मैं नहीं देख सकता कि इससे ओवरफ्लो कैसे होगा। जब मैं कुछ अलग इनपुट के लिए अपने दिमाग में एल्गोरिदम चलाता हूं, तो मुझे एरे इंडेक्स से बाहर जाने वाले मध्य का मूल्य दिखाई नहीं देता है।

तो, किस मामले में अतिप्रवाह होता है?

Answer 1

यह post इस प्रसिद्ध बग को बहुत विस्तार से शामिल करता है। जैसा कि अन्य ने कहा है कि यह एक अतिप्रवाह मुद्दा है। (उदाहरण के लिए, में एक मूल्य के लिए खोज

int mid = low + ((high - low)/2); 

// Alternatively 
int mid = (low + high) >>> 1; 

यह भी है कि इस मामले में नकारात्मक सूचकांक अनुमति दी जाती है शायद उल्लेख के लायक है, या शायद यह भी एक सरणी है कि खोजा जा रहा है नहीं है: ठीक लिंक पर सिफारिश की इस प्रकार है कुछ पूर्णांक सीमा कुछ शर्त को संतुष्ट करती है), ऊपर दिया गया कोड भी सही नहीं हो सकता है। इस मामले में,

(low < 0 && high > 0) ? (low + high)/2 : low + (high - low)/2 

के रूप में बदसूरत के रूप में कुछ आवश्यक हो सकता है। एक अच्छा उदाहरण है जो पूरे Integer.MIN_VALUE - Integer.MAX_VALUE रेंज पर बस एक बाइनरी खोज कर रहा है।

Answer 2

संभावित ओवरफ़्लो l+u अतिरिक्त में है।

यह वास्तव में जेडीके में बाइनरी खोज के a bug in early versions था।

Answer 3

समस्या यह है कि (l+u) का मूल्यांकन पहले किया गया है, और अतिप्रवाह int हो सकता है, इसलिए (l+u)/2 गलत मान वापस कर देगा।

Answer 4

जेफ ने इस बग के बारे में पढ़ने के लिए वास्तव में post का सुझाव दिया है, तो सारांश सारांश यदि आप त्वरित अवलोकन चाहते हैं।

प्रोग्रामिंग में मोती बेंटले का कहना है कि समान रेखा "एल और यू के औसत से मीटर सेट करती है, जो निकटतम पूर्णांक तक गिर जाती है।" इसके चेहरे पर, यह दावा सही दिखाई दे सकता है, लेकिन यह int चर के उच्च मानों के लिए कम और उच्च के लिए विफल रहता है। विशेष रूप से, यह विफल रहता है यदि निम्न और उच्चतम योग अधिकतम सकारात्मक int मान (2^31 - 1) से अधिक है। राशि ऋणात्मक मूल्य पर बहती है, और मूल्य दो से विभाजित होने पर ऋणात्मक रहता है। सी में यह अप्रत्याशित परिणामों के साथ सीमाओं से बाहर एक सरणी सूचकांक का कारण बनता है। जावा में, यह ArrayIndexOutOfBoundsException फेंकता है।