https://leetcode.com/problems/find-peak-element/description/

Tag: Array/List, Binary Search

Key Points:

1. The log(n) complexity implies the binary search in most cases

2. This condition is crucial when deciding which side to choose during binary search

   <aside> 💡

   nums[i] != nums[i + 1] for all valid i.

   </aside>

3. Use the binary search template to prevent accidental infinite loop

4. If a point is not a peak:

   1. A peak candidate must exist on its right side if its right neighbor is larger.
   2. Otherwise, on its left side

5. Pay special attention to boundary conditions when:

   1. check if a point is a peak
   2. move the left/right pointer

Solution:

def findPeakElement(self, nums: List[int]) -> int:
	  if not nums:
	      return -1

	  if len(nums) == 1:
			  return 0

	  left, right = 0, len(nums) - 1
	  
	  while left + 1 < right:
			  # Python integer addition won't overflow. For other language, 
			  # it's suggested to write as: mid = left + (right - left) // 2
	      mid = (left + right) // 2 
	      if self.isPeak(nums, mid):
	          return mid
	      # mid is not peak because its left candidate is larger,
	      # the peak will be on its left side. Note when mid = 0 and it's not peak,
	      # the only reason would be its larger right neighbor.
	      # That is caught by the second elif below and need no special handling
	      elif mid > 0 and nums[mid - 1] > nums[mid]:
	          right = mid
	      elif mid < len(nums) - 1 and nums[mid + 1] > nums[mid]:
	          left = mid
	      else:
	          raise Exception("Invalid input")

	  if self.isPeak(nums, left):
	      return left
	  else:
	      return right
	
	def isPeak(self, nums, idx):
		# Handle the boundary condition
	  if idx == 0:
	      return nums[idx] > nums[1]
	  elif idx == len(nums) - 1:
	      return nums[idx - 1] < nums[idx]
	  else:
	      return nums[idx] > max(nums[idx-1], nums[idx+1])