Нахождения минимума в отсортированный, повернутый массив


Дан массив, который сначала отсортированный неубыванию, а затем поворачивается право на неопределенное количество раз, найти индекс минимального эффективно элементом. Если существует несколько таких минимальных элементов, вернуться индекс любой.

Идея: концептуально разделить массив на две части: "большой" подраздел (слева), который состоит из большого числа привезли сюда с крайнего правого на поворот, а "мелкие" части, которая начинается с наименьшего элемента. Мы всегда можем сказать, в какой части мы и двигаться влево/вправо соответственно.

Примечания: если массив имеет несколько минимальных элементов, индекс слева в "правой" части возвращается.

int getMinimIndex (const int *const a, size_t left, size_t right)
{
        assert(left<= right);

        // Special cases:
        // 1 If left & right are same , return 
        if (left ==right)
                return left;

        // 2 For an array of size 2, return the index of minimal element
        if (left == right - 1)
                return a[left]<=a[right]?left:right;

        // 3 If the array wasn't rotated at all, 
        if (a[left] < a[right])
                return left;


        // General case
        // Go to the middle of the array
        size_t mid = (left + right) >> 1;

        // If we stepped into the "larger" subarray, we came too far, 
        // hence search the right subpart    
        if (a[left] <= a[mid] )
                return getMinimIndex(a, mid, right);
        else
        // We're still in the "smaller" subarray, hence search left subpart
                return getMinimIndex(a,left, mid);
}

Модульные тесты:

\#define lastIndex(a)  ((sizeof(a)/sizeof(a[0]))-1)

int main()
{
        int a1[] = {7,8,9,10,11,3};
        int a2[] = {1};
        int a3[] = {2,3,1};
        int a4[] = {2,1};
        int a5[] = {2,2,2,2,2};
        int a6[] = {6,7,7,7,8,8,6,6,6};
        int a7[] = {1,2,3,4};

        printf("\n%d", getMinimIndex(a1,0, lastIndex(a1))); // 5
        printf("\n%d", getMinimIndex(a2,0, lastIndex(a2))); // 0
        printf("\n%d", getMinimIndex(a3,0, lastIndex(a3))); // 2
        printf("\n%d", getMinimIndex(a4,0, lastIndex(a4))); // 1
        printf("\n%d", getMinimIndex(a5,0, lastIndex(a5))); // 3 
        printf("\n%d", getMinimIndex(a6,0, lastIndex(a6))); // 6
        printf("\n%d", getMinimIndex(a7,0, lastIndex(a7))); // 0

        return 0;

}


2471
11
задан 29 марта 2011 в 02:03 Источник Поделиться
Комментарии
3 ответа

Алгоритм работает неправильно.

Она не на следующее:

int a1[] = {10,1,10,10,10,10,10};

printf("\n%d", getMinimIndex(a1,0, lastIndex(a1))); // 5

Он печатает 5 вместо 1.

Проблема в том случае, если элементы могут повторяться, то предположение, что мы можем повторить на левую или правую половину неправильно.

В самом деле, если элементы могут повторяться, любой алгоритм будет, в худшем случае Омега(н), а у тебя-всегда за o(logn), то значит это неправильно.

7
ответ дан 31 марта 2011 в 12:03 Источник Поделиться

Ваш алгоритм работает для последовательностей, которые строго возрастающей (как @дебил указывает). Если эффективность-это внимание, вы, возможно, пожелает использовать итерации вместо рекурсии.

int getMinimIndex (const int *const a, size_t left, size_t right)
{
while (1)
{
assert(left<= right);

// Special cases:
// 1 If left & right are same , return
if (left ==right)
return left;

// 2 For an array of size 2, return the index of minimal element
if (left == right - 1)
return a[left]<=a[right]?left:right;

// 3 If the array wasn't rotated at all,
if (a[left] < a[right])
return left;

// General case
// Go to the middle of the array
size_t mid = (left + right) >> 1;

// If we stepped into the "larger" subarray, we came too far,
// hence search the right subpart
if (a[left] <= a[mid])
left = mid;
else
// We're still in the "smaller" subarray, hence search left subpart
right = mid;
}
}

6
ответ дан 29 марта 2011 в 03:03 Источник Поделиться

if (a[left] <= a[mid] )
return getMinimIndex(a, mid, right);
else
// We're still in the "smaller" subarray, hence search left subpart
return getMinimIndex(a,left, mid);

Во второй строке, кажется, что он может быть слева = середина + 1. Ведь мы уже знаем, что в середине является частью большего подмассива, так что мы можем пропустить его и найти, начиная со следующего элемента.

5
ответ дан 29 марта 2011 в 09:03 Источник Поделиться