Finding the maximum value in an array with increasing values ​​on either side of the index

Question

I am trying to solve a problem that requires finding the maximum value in the array. An array cannot be distorted by brute force, because it is very large (over 100,000,000 elements), so I'm trying to create a modified version of a binary search to find the maximum.

The specific attributes of the array are:

• The array is round
• Starting from the index of the minimum value in the array, all values ​​that pass 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 minimum value index is opposite the maximum value index

Examples of some arrays (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}

- 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

0 0 0 0 0 0 0 1 0

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