Поиск минимума в сортированном, повернутом массиве

  

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

     

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

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

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;

}
11 голосов | спросил Ganesh 29 MaramTue, 29 Mar 2011 06:19:39 +04002011-03-29T06:19:39+04:0006 2011, 06:19:39

4 ответа


7

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

Не удается выполнить следующие действия:

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

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

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

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

Фактически, если элементы могут повторяться, любой алгоритм будет в худшем случае Omega (n), а ваш всегда O (logn), поэтому он неверен.

ответил Aryabhata 31 MaramThu, 31 Mar 2011 04:58:39 +04002011-03-31T04:58:39+04:0004 2011, 04:58:39
6

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

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;
    }
}
ответил Adeel Zafar Soomro 29 MaramTue, 29 Mar 2011 07:48:26 +04002011-03-29T07:48:26+04:0007 2011, 07:48:26
5
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);

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

ответил Snowbear 29 MarpmTue, 29 Mar 2011 13:46:18 +04002011-03-29T13:46:18+04:0001 2011, 13:46:18
1

Почему не просто?

int minimumIndex(size_t arrayLength, const int* const array){
    int lowestIndex = 0;
    for(size_t curIndex = 0; curIndex < arrayLength; ++curIndex){
        if(array[curIndex] < array[lowestIndex]){
            lowestIndex = curIndex;
        }
    }
    return lowestIndex;
}
  • Выполняется с сложностью O (n), и если использовать действительно огромные массивы и старое оборудование все равно будет достаточно быстро.
  • Даже если весь массив является одним и тем же значением, он будет только когда-либо возвращать первый индекс.
  • Неважно, отсортирован ли массив или нет.
  • Если не предоставляется недопустимый ввод, он всегда будет работать правильно.
  • Допустимо корректно, даже если числовой тип в массиве изменен.
  • Использует 0 дополнительную память, 0 указателей.
  • Не рекурсивно, поэтому он никогда не ударит по глубине рекурсии.
  • Только вызов одной функции , поскольку для каждого рекурсивного вызова требуется новый стек стека, скачок и инструкция ret. Плюс любая память выделяет /deallocs из-за того, что она является новой областью.

Если это просто для ударов, не стесняйтесь игнорировать этот ответ (я недавно реализовал Merge Sort «просто для ударов», поэтому я думаю, что понимаю, почему вы его написали)

ответил DJHenjin 22 PM00000080000005731 2016, 20:14:57

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132