चक्रीय सॉर्टेड सरणी में न्यूनतम तत्व ढूंढना

Question

मैंने चक्रीय सॉर्ट किए गए सरणी में न्यूनतम तत्व को खोजने के लिए निम्न कोड का प्रयास किया है। लेकिन यह विफल रहता है जब कम = 1 और उच्च = 2 क्योंकि मध्य हमेशा 1 होता है और एक [मध्य] = एक [1] हमेशा [उच्च] से अधिक होता है।

मैं समाधान खोजने के लिए यहां बाइनरी खोज का उपयोग करने की कोशिश कर रहा हूं।

//finding the minim element in the cyclic sorted array 
int arrC[]={10,13,1,3,4,5,8}; 
int low=0,high =6; 
int mid=0,reset =1; 
while (low < high) 
{ 
    mid = (low+ high)/2; 
    if (arrC[mid]>arrC[high]) 
    { 
     low = mid; 
    } 
    else if (arrC[mid] < arrC[high]) 
    { 
     high = mid; 

    } 
} 
printf("minimum element is %d",arrC[mid+1]); 

Answer 1

एक सामान्य द्विआधारी खोज का उपयोग करें, लेकिन अगर arrC[high] < arrC[low], चारों ओर रैप के लिए खाते की अनन्तता के रूप में arrC[high] व्यवहार करते हैं।

if (arrC[mid]>arrC[high]) 

करने के लिए::

if (arrC[high] < arrC[low] || arrC[mid] > arrC[high]) 

Answer 2

अपने कोड के साथ 2 समस्याओं

• Paulpro द्वारा बताया के रूप में ... इलाज ARRC [उच्च] के रूप में कर रहे हैं कि सिर्फ लाइन बदलने के ऐसा करने के लिए अनंतता ..
• इसके अलावा मैं आपको

का उपयोग करने का सुझाव भी दूंगा

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

(low+high)/2 प्रयोग न करें। इससे योग पूर्णांक की सीमा से अधिक हो सकता है और इसके परिणामस्वरूप ऋणात्मक मूल्य होगा। एक और कारण आपका कोड असफल हो सकता है।

Answer 3

#include <stdio.h> 

int main(void){ 
//finding the minim element in the cyclic sorted array 
    int arrC[]={10,13,1,3,4,5,8}; 
    int low=0, high = sizeof(arrC)/sizeof(*arrC)-1; 
    int range; 
    if(arrC[low]>=arrC[high]){ 
     while (range = (high - low)/2){// range = range/2; 
      if(arrC[high - range] <= arrC[high]){ 
       high -= range; 
      } else { 
       low = high - range; 
       continue; 
      } 
      if(arrC[low] <= arrC[low + range]){ 
       low += range; 
      } else { 
       high = low + range; 
      } 
     } 
     if(high == low + 1){ 
      low = high; 
     } 
    } 
    printf("minimum element is %d",arrC[low]);//1 
    return 0; 
} 

ध्यान दें: यह बस खोज रेंज को आधा करने के लिए जब एक ही मूल्य है, तो आदेश दिया डेटा में शामिल है, क्योंकि यह संभव आसानी से दिशा खोजे जाने के लिए निर्धारित करने के लिए नहीं है संभव नहीं है। लेकिन यह संभव है यदि एक ही मूल्य शामिल नहीं है।