Finding max value in array with increasing values from either side of an index

Question

I am trying to solve a problem which requires finding the maximum value in an array. The array cannot be brute force searched as it is very large (over 100,000,000 elements) so I am attempting to create a modified version of binary search to find the maximum.

The specific attributes of the array are:

• The array is circular
• Starting from the index of minimum value in the array all values past this index will either increase or remain constant until the index of the maximum value. From here the values will either remain constant or decrease
• The index of the minimum value is opposite the index of the maximum value

Examples of some arrays are (All equivalent arrays):

• {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}

Does anyone have any ideas as to solve this problem in approximately O(logN) time?

How array values are calculated:

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;
}

• Swapnil: Can you clarify "The index of the minimum value is opposite the index of the maximum value". I didn't quite get the opposite part.
• 1qaz0okm: Basically say the index of the minimum value is 6 the index of the maximum value will be (6 + n /2) % n

Answer 1

If you allow lists of n-1 times the same number and 1 time a greater one, e.g.

5 5 5 5 5 5 5 6 5,

then I claim that you cannot, in general, solve the problem in O(log n) time, as the problem is equivalent to searching for a 1 in

0 0 0 0 0 0 0 1 0

So you're effectively searching for a particular entry in an unsorted list, which needs O(n) time.

You can, of course, speed up the algorithm for special cases, e.g. by combining a linear search with a binary search, allowing you to skip strictly decreasing sub-sequences of the list.

The following solution is wrong, see comments.

Pseudo-code:

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;

• 1qaz0okm: I had something pretty similar to this but it doesn't work for the following example (or any array where there is 3 of the same number in a row): {5, 5, 5, 5, 5, 5, 6, 5}
• JohnB: Yes, you're right. My solution is wrong. It now seems to me that you could prove that it's not possible to solve the problem in O(log n) time, as the 6 might be at any of the n places and that, in general, you cannot determine where it is other than by looking at (nearly) all the elements of the array!? You're essentially searching for a one in an unsorted list of n-1 zeros and 1 one.
• 1qaz0okm: So my time spent trying to find a solution was in vain. Time to find another way to solve the problem then :(.
• Swapnil: @JohnB Agreed. We cannot eliminate any half of the array here, so O(n) is not possible in the worst case. However, if not more than two consecutive duplicates are present, this might work.
• JohnB: If the special case is not frequent, it might make sense to speed up the search by somehow combining it with a binary search. Suppose the list has 16 elements: If ary [1] > ary [0] and ary [4] > ary [3], then, e.g., you need not look at ary [2].