क्या बाइनरी खोज एल्गोरिदम के प्रति पुनरावृत्ति प्रति केवल एक तुलना होना संभव है?

Question

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

if (key == a[mid]) then found; 

else if (key < a[mid]) then binary_search(a[],left,mid-1); 
     else binary_search(a[],mid+1,right); 

वहाँ एक रास्ता है जिसके द्वारा मैं ऊपर दो के बजाय सिर्फ एक ही तुलना कर सकते हैं है।

-

धन्यवाद

Alok.Kr.

Answer 1

देखें:

http://en.wikipedia.org/wiki/Binary_search_algorithm#Single_comparison_per_iteration

विकि से लिया:

low = 0 
    high = N 
    while (low < high) { 
     mid = low + ((high - low)/2) 
     if (A[mid] < value) 
      low = mid + 1; 
     else 
      //can't be high = mid-1: here A[mid] >= value, 
      //so high can't be < mid if A[mid] == value 
      high = mid; 
    } 
    // high == low, using high or low depends on taste 
    if ((low < N) && (A[low] == value)) 
     return low // found 
    else 
     return -1 // not found 

पेशेवरों/विकी है विपक्ष: "यह दृष्टिकोण जल्दी समाप्ति की संभावना एक मैच की खोज पर foregoes, इस प्रकार सफल खोजों में अपेक्षित लॉग 2 (एन) - 1 पुनरावृत्तियों के बजाय लॉग 2 (एन) पुनरावृत्तियों होते हैं। दूसरी तरफ, यह कार्यान्वयन कम तुलना करता है: लॉग 2 (एन) ली है आठ से अधिक एन के लिए 1 · 5 (लॉग 2 (एन) -1) के दो परीक्षण कार्यान्वयन के लिए तुलना की अपेक्षित संख्या की तुलना में एसएस। "

Answer 2

यह रिकर्सिव एल्गोरिदम है। पहली तुलना स्टॉप मानदंड और दूसरी वास्तविक खोज है, इसलिए आप उन्हें हटा नहीं सकते हैं।

सबसे पहले आप पूछते हैं कि जब भी आप तत्व पहले से ही पाए जाते हैं और दूसरे में तत्व के लिए सरणी के भाग में भाग लेते हैं। तो आप केवल एक तुलना के आधार पर उन निर्णयों को नहीं बना सकते हैं।

Answer 3

हां। रिकर्सिव कॉल से बस mid को खत्म न करें।

if (left == right) return NULL; 
if (left + 1 == right) return key == a[left]? &a[left] : NULL; 

mid = left + (right - left/2); 

if (key < a[mid]) return binary_search(a[],left,mid-1); 
else return binary_search(a[],mid,right); // include `mid` in next round 

आपको ओ (लॉगएन) प्रदर्शन प्राप्त करने के लिए केवल प्रत्येक रिकर्सन के साथ सेट के आधे को खत्म करने की आवश्यकता है। आप आधा + 1 को हटाकर ऊपर और परे जा रहे हैं।

आप केवल प्रत्यावर्तन दौरान < उपयोग करते हैं, कम से कम एल्गोरिथ्म तत्व है जो है key से कम नहीं है (लेकिन key से अधिक हो सकता है) मिल जाएगा। एक समान समानता परीक्षण करके समाप्त करें।

Answer 4

कोडांतरक में, आप कर सकते हैं:

cmp key,a[mid] 
beq found 
bge else 

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

Answer 5

पहली चीजें पहले: क्या आपको प्रोग्राम को अनुकूलित करने की आवश्यकता है? क्या आपको यह जानने के लिए मापा गया है कि आपको इसे कहां करने की आवश्यकता है? क्या यह इस समारोह में है?

आदिम प्रकारों के लिए दूसरी तुलना उतनी तेजी से एक ऑपरेशन जितनी हो जाती है। तुलना की उच्च लागत तत्व को उचित रजिस्टर में लोड कर रही है, और इसकी पहली तुलना के लिए आवश्यक है। एक बार यह तुलना निष्पादित हो जाने के बाद, मान पहले से ही एक रजिस्टर में है और दूसरा ऑपरेशन एक एकल प्रोसेसर निर्देश और शाखा गलतफहमी की संभावित लागत लेता है।

अभिन्न प्रकार मानते हुए, एल्गोरिदम के प्रोसेसर समय में लागत शायद रिकर्सिव कॉल की लागत का प्रभुत्व है यदि संकलक पूंछ-रिकर्सन ऑप्टिमाइज़ेशन करने में सक्षम नहीं है। यदि आपको वास्तव में इसे अनुकूलित करने की आवश्यकता है, तो सभी अनुकूलन झंडे के साथ संकलन करने का प्रयास करें और असेंबलर का विश्लेषण करने के लिए विश्लेषण करें कि पूंछ-रिकर्सन ऑप्टिमाइज़ेशन लागू किया जा रहा है या नहीं। यदि नहीं, तो मैन्युअल रूप से पुनरावृत्ति से पुनरावृत्त करने के लिए एल्गोरिदम को रूपांतरित करें।

इसमें दो प्रभाव होंगे: कोड अस्पष्ट करें (एक साफ समाधान को संशोधित करने से बचें जब तक कि आपको वास्तव में आवश्यकता न हो) और यह फ़ंक्शन कॉल से बचें।

आप सी ++ की बात कर रहे हैं, और प्रकार जटिल है और अतिभारित तुलना ऑपरेटरों महंगा, प्रदर्शन में सबसे तेजी से बढ़ावा एक compare विधि है कि के लिए एक नकारात्मक संख्या वापस आ जाएगी लागू कर रहा है कर रहे हैं से कम, 0 बराबर के लिए , और एक सकारात्मक संख्या से अधिक है। फिर तुलना से पहले परिणाम का प्रीकंप्यूट करें और फिर पूर्णांक केवल जांच करें। इससे वास्तविक वस्तुओं के साथ वास्तविक वस्तुओं की एक प्रसंस्करण में एल्गोरिदम की समग्र लागत को हटा दिया जाएगा और आपको मूल धारणा में वापस सेट कर दिया जाएगा।

Answer 6

for (step = 0; step < n; step <<= 1); 

for (i = 0; step; step >>= 1) 
    if (i + step < n && v[i + step] <= x) 
     i += step; 

Answer 7

ठीक है, इस में Adobe एक साक्षात्कार सवाल था, और मैं सिर्फ ऐसा करने के तरीके यह पता लगाने की कोशिश कर रहा था।

अब मैं इसे का हल मिल गया है, तो मैं, पोस्टिंग

void binary_search (int a[] , int low , int high , int key) 
{ 
    int mid = (low+high)/2; 

    if (key == a[mid]) { 
     printf ("Number Found\n"); 
     return; 
    } 

    else { 
     int sign = Calc_sign (key-a[mid]); 
     low = low*sign + (1-sign)*mid; 
     high = mid*sign + (1-sign)*right; 
     binary_search (a,low,high,key); 
    } 
} 

int Calc_sign(int a) 
{ 
    return ((a & 80000000) >> 31); 
} 

तो कोड में वहाँ केवल जाँच के लिए एक तुलना हो सकता है अगर keyvalue मध्य तत्व को eqaul है हूँ।

-

धन्यवाद

आलोक Kr।