Найти точку поворота в отсортированном массиве

Question

Я пытаюсь найти точку поворота в отсортированном массиве через модифицированный двоичный поиск.

Рассмотрим этого массив int values[9]={7, 8, 9, 1, 2, 3, 4, 5, 6}; Точка вращения здесь имеет индекс = 3 т.е. в 9.

Я написал эту функцию для указанных выше операций.

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

Если элементы int values[9]={7, 8, 9, 1, 2, 3, 4, 5, 6};Выход: 4, 1 (Неправильный)

int values[9]={7, 8, 9, 10, 2, 3, 4, 5, 6};Выход: 4, 10 (Правильное)

Точка вращения, которая находится на даже место найдено правильно, тогда как в другом случае он находит следующий элемент. Что мне не хватает в приведенном выше коде?

Answer 1

Это работает:

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

Это должно сработать.