c++ - 在排序数组中查找旋转点

Question

我试图通过修改后的二进制搜索在排序数组中定位旋转点。

考虑这个数组 int values[9]={7, 8, 9, 1, 2, 3, 4, 5, 6}; 这里的旋转点在 index = 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;
}