znajdowanie minimalnego elementu w cyklicznej posortowanej tablicy

Question

Próbowałem następującego kodu, aby znaleźć minimalny element w cyklicznej posortowanej tablicy. Ale zawiedzie, gdy niski = 1 i wysoki = 2, ponieważ środek jest zawsze 1, a [środkowy] = a [1] jest zawsze większy niż a [wysoki].

Próbuję użyć wyszukiwania binarnego tutaj, aby znaleźć rozwiązanie.

//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

Użyć zwykłej przeszukiwanie binarne, ale jeśli arrC[high] < arrC[low] traktować arrC[high] jako nieskończoności do odpowiedzialności za zawinięcia. Aby to zrobić wystarczy zmienić linię:

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

Do:

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

Answer 2

Są 2 problemy z kodem

• Jak wskazano przez Paulpro ... traktują ARRC [Wysoki] jak nieskończoność ..
• Poza tym proponuję użyć także

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

Nie używaj (low+high)/2. Może to spowodować, że suma przekroczy limit liczby całkowitej i spowoduje wynik ujemny. Jeszcze jeden powód, dla którego twój kod może zawieść.

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; 
} 

Uwaga: To nie jest możliwe, aby zmniejszyć o połowę zakres wyszukiwania po prostu, gdy ta sama wartość jest wliczone w uporządkowanych danych w przypadku, ponieważ nie jest możliwe, aby łatwo określić kierunek być przeszukane. Ale jest to możliwe, jeśli ta sama wartość nie jest uwzględniona.