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

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. — Swapnil
– Swapnil, Commented Jul 27, 2014 at 10:46
Basically say the index of the minimum value is 6 the index of the maximum value will be (6 + n /2) % n; — 1qaz0okm
– 1qaz0okm, Commented Jul 27, 2014 at 10:50

JohnB · Accepted Answer · 2014-07-27 11:05:17Z

4

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;

edited Jul 27, 2014 at 11:05

answered Jul 27, 2014 at 10:32

JohnB

13.8k6 gold badges42 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

1qaz0okm Over a year ago

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 Over a year ago

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 Over a year ago

So my time spent trying to find a solution was in vain. Time to find another way to solve the problem then :(.

Swapnil Over a year ago

@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 Over a year ago

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].

|

Collectives™ on Stack Overflow

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

1 Answer 1

6 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Related