Recherche du point de rotation dans le tableau trié

Question

J'essaie de localiser le point de rotation dans un tableau trié via une recherche binaire modifiée.

Tenir compte de ce tableau int values[9]={7, 8, 9, 1, 2, 3, 4, 5, 6}; Le point de rotation est ici à l'index = 3 i.e. à 9.

J'ai écrit cette fonction pour l'opération ci-dessus.

void FindRotationPoint(int values[], int numvalues) 
{ 
    int first =0; 
    int last = numvalues-1; 
    int middle; 
    bool moreTosearch= (first<=last); 
    while(first<=last) 
    { 
     middle = (first+last)/2; 
     if(values[0]>values[middle]) //Keep looking right if the middle value in array is greater than first 
     { 
      last = middle-1; 
     } 
     if (values[0]<values[middle]) //Keep looking left if the middle value in array is less than first 
     { 
      first = middle+1; 
     } 
    } 
    cout<<middle+1<<endl; 
    cout<<values[middle]; 
} 

Si les éléments sont int values[9]={7, 8, 9, 1, 2, 3, 4, 5, 6};sortie: 4, 1 (erronées)

int values[9]={7, 8, 9, 10, 2, 3, 4, 5, 6};sortie: 4, 10 (Correct)

Le point de rotation qui est à un même endroit est trouvé correct alors que dans l'autre cas, il trouve l'élément suivant. Qu'est-ce qui me manque dans le code ci-dessus?

Answer 1

Cela fonctionne:

void FindRotationPoint(int values[], int numvalues) 
{ 
    int first =0; 
    int last = numvalues-1; 
    int middle=0; 
    bool moreTosearch= (first<=last); 
    while(first<last) 
    { 
     middle = (first+last)/2; 
     if(values[first]>=values[middle]) //Keep looking right if the middle value in array is greater than first 
     { 
      last = middle; 
      cout<<"first>middle: "<<first<<" "<<middle<<" "<<last<<"\n"; 
     } 
     else if (values[middle]>=values[last]) //Keep looking left if the middle value in array is less than first 
     { 
      first = middle; 
      cout<<"middle<last: "<<first<<" "<<middle<<" "<<last<<"\n"; 
     } 
    } 
    cout<<middle+1<<endl; 
    cout<<values[middle]; 
} 

int main() 
{ 
int values[9]={7, 8, 9, 1, 2, 3, 4, 5, 6}; 

FindRotationPoint(values, 9); 
return 0; 
} 

Answer 2

void FindRotationPoint(int values[], int numvalues) 
{ 
    int first =0; 
    int last = numvalues-1; 
    int middle; 
    bool moreTosearch= (first<=last); 
    while(moreTosearch) 
    { 
     middle = (first+last)/2; 
     if(middle == first) break; 
     if(values[0]>values[middle]) //Keep looking right if the middle value in array is greater than first 
     { 
      last = middle; 
      moreTosearch= (first<=last); 
     } 
     if (values[0]<values[middle]) //Keep looking left if the middle value in array is less than first 
     { 
      first = middle; 
      moreTosearch= (first<=last); 
     } 
    } 
} 

Cela devrait fonctionner.