Python Example of Finding the Local Maximum of an Array

Finding the local maximum of an array

Given an array A[0...N-1] with no repeated elements, find a local maximum of the array. Provision: the value outside the array boundary is infinitesimal. That is, A[0] > A[-1] and A[N-1] > A[N].

Clearly, traversing once finds the global maximum, which is clearly a local maximum.

Is there a faster way to do this?

Algorithm Description

Use the indexes left and right to point to the beginning and end of the array, respectively.

Find the midpoint mid = ( left + right ) / 2

A[mid] > A[mid+1], discard second half: right=mid

A[mid+1] > A[mid], discard first half: left=mid+1

Recursion until left==right

The time complexity is O(logN).

Python code

def local_maximum(li):
  if li is None:
    return
  left = 0
  right = len(li) - 1
  while left < right:
    mid = int((left + right) / 2)
    if li[mid] > li[mid + 1]:
      right = mid
    else:
      left = mid + 1
  return li[left]


if __name__ == '__main__':
  li = [1, 5, 2, 3, 4, 0]
  result = local_maximum(li)
  print(result)

Output: 4

The above example of this Python for the local maximum of the array is all that I have shared with you, I hope it will give you a reference, and I hope you will support me more.