Нахождение точки вращения в отсортированном массиве - PullRequest
Новая
       11

Нахождение точки вращения в отсортированном массиве

1 голос
/ 10 сентября 2011

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

Рассмотрим этот массив 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 (правильно)

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

Ответы [ 2 ]

0 голосов
/ 10 сентября 2011

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

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;
}
0 голосов
/ 10 сентября 2011 
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);
        }
    }
}

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

...