बाइनरी सर्च कार्यान्वयन में एक समस्या

हम जानते हैं कि बाइनरी सर्च एल्गोरिदम रैखिक खोज एल्गोरिदम से बेहतर है। यह एल्गोरिदम निष्पादित होने में O(log n) समय लेता है। हालांकि अधिकांश मामलों में कार्यान्वित कोड में कुछ समस्या होती है। आइए एक बाइनरी सर्च एल्गोरिदम फ़ंक्शन पर विचार करें जैसे नीचे -

उदाहरण

int binarySearch(int array[], int start, int end, int key){     if(start <= end){         int mid = (start + end) /2); //mid location of the list         if(array[mid] == key)             return mid;         if(array[mid] > key)             return binarySearch(array, start, mid-1, key);             return binarySearch(array, mid+1, end, key);     }     return -1; }

यह एल्गोरिदम तब तक ठीक काम करेगा जब तक स्टार्ट और एंड एक बड़ी संख्या तक नहीं पहुंच जाते। यदि (स्टार्ट + एंड) 2^32 - 1 के मान से अधिक हो जाता है तो यह लपेटने के बाद एक नकारात्मक संख्या लौटा सकता है। और चूंकि नकारात्मक संख्याएं सरणी सूचकांक के रूप में समर्थित नहीं हैं, तो यह कुछ समस्या पैदा कर सकता है।

इस समस्या को दूर करने के लिए, कुछ अलग तरीके हैं।

विधि 1

int mid = start + ((end - start) / 2)

दूसरी विधि केवल जावा में काम करेगी क्योंकि C या C++ में >>> ऑपरेटर नहीं है।

विधि 2 (केवल जावा)

int mid = (start + end) >>> 1

चूंकि >>> C या C++ में समर्थित नहीं है, तो हम निम्नलिखित विधि का उपयोग कर सकते हैं।

विधि 3

int mid = ((unsigned int) low + (unsigned int) high) >> 1