ソートされた配列内の回転点を見つける

Question

私は、ソートされた配列内の回転点を、変更されたバイナリ検索によって探し出そうとしています。

ここで、回転の点は、私は上記の操作のために、この機能を書いた9

でインデックス= 3すなわちであり、この配列int values[9]={7, 8, 9, 1, 2, 3, 4, 5, 6}; 検討します。

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

これは動作するはずです。