Suppose we maintain an array A of n int values as follows:
A[0] < A[1] < ...< A[i] > A[i + 1] > A[i + 2] > ...> A[n - 1]
The ith element is the maximum in the array.What would be the lowest big-Oh notation for finding that element? Consider a variation of the binary search.

Question

Quizplus · Accepted Answer

Since the array is sorted and the maximum element is known to be at index i, we can use binary search to find the maximum element in O(log n) time complexity.

Suppose We Maintain an Array a of N Int Values