在排序數組中查找旋轉點

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

這應該工作。