從索引的任意一側查找數組中的最大值

Question

我試圖解決一個需要在數組中找到最大值的問題。該數組不能進行強力搜索，因爲它非常大（超過100,000,000個元素），所以我試圖創建二進制搜索的修改版本以查找最大值。

數組的特定屬性是：

• 陣列是圓形
• 從最小值的陣列中的索引開始過去該索引的所有值將增加或保持不變，直到所述指數最大值。從這裏的值將保持不變或減少
• 最小值的索引是最大值

某些陣列的實例是（所有等效陣列）的索引相對：

• {1, 2, 3, 4, 5, 5, 4, 3, 2, 1}
• {5, 4, 3, 2, 1, 1, 2, 3, 4, 5}
• {3, 4, 5, 5, 4, 3, 2, 1, 1, 2}

有沒有人有任何想法來解決這個問題在大約O（logN）時間？

如何計算數組值：

unsigned long long calculateArrayValue(unsigned long long location, unsigned long long n, unsigned long long arrayLength, unsigned long long* arrayIndices, unsigned long long* locationMagnitude) { 
    unsigned long long value = 0; 
    unsigned long long halfArrayLength = arrayLength/ 2; 
    unsigned long long difference; 
    for (unsigned long long i = 0; i < n; i++) { 
     if (arrayIndices[i] > location) { 
      difference = arrayIndices[i] - location; 
     } else { 
      difference = location - houseLocations[i]; 
     } 
     if (difference > halfArrayLength) { 
      difference = arrayLength - difference; 
     } 
     value += difference * locationMagnitude[i]; 
    } 

    return value; 
} 

Answer 1

如果允許相同數量的N-1次和1次較大之一，例如列表

5 5 5 5 5 5 5 6 5，

然後我要求，你不能在一般情況下，解決問題在O（log n）的時間，因爲該問題是相當於搜索用於在1

所以你有效地尋找在未排序列表中的特定條目，該條目需要O（n）的時間。

當然，您可以加快特殊情況下的算法，例如，通過將線性搜索與二分搜索相結合，可以跳過嚴格減少列表的子序列。

以下解決方法是錯誤的，請參閱註釋。

僞代碼：

int next (int i) { 
    return i + 1 < length ? i + 1 : 0; 
} 

int prev (int i) { 
    return i - 1 < 0 ? length : i - 1; 
} 

int lower = 0; 
int upper = length - 1; 
int tmp; 

while (true) { 
    tmp = (upper + lower)/2; 
    if ((ary [prev(tmp)] <= ary [tmp]) && (ary [next(tmp)] <= ary [tmp])) break; 

    if (ary [prev(tmp)] <= ary [tmp]) { 
     lower = tmp; 
    } else if (ary [next(tmp)] <= ary [tmp]) { 
     upper = tmp; 
    } else { 
     /* we have found a minimum! */ 
     tmp = length - 1 - tmp; 
     break; 
    } 
} 

int maximum_index = tmp;