A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:


Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:


Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.


Note:

Your solution should be in logarithmic complexity.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Starter code: class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def findPeakElement(self, nums):
		if not nums:
			return -1
		start = 0
		end = len(nums) - 1
		while start + 1 < end:
			mid = (start + end) // 2
			if nums[mid] > nums[mid - 1]:
				if nums[mid] > nums[mid + 1]:
					return mid
				else:
					start = mid
			else:
				end = mid
		if nums[start] > nums[end]:
			return start
		else:
			return end


class Solution:

	def findPeakElement(self, nums):
		if len(nums) == 0:
			return None
		if len(nums) == 1:
			return 0
		if len(nums) == 2:
			return 0 if nums[0] > nums[1] else 1
		res = list()
		if nums[0] > nums[1]:
			return 0
		if nums[-1] > nums[-2]:
			return len(nums) - 1
		for i in range(1, len(nums) - 1):
			pre = nums[i - 1]
			cur = nums[i]
			nex = nums[i + 1]
			if cur > pre and cur > nex:
				return i


class Solution:

	def findPeakElement(self, nums):
		(begin, end) = (0, 2)
		if len(nums) == 1:
			return 0
		while end < len(nums):
			mid = (begin + end) // 2
			if nums[mid] > nums[begin] and nums[mid] > nums[end]:
				return mid
			begin += 1
			end += 1
		if nums[0] > nums[1]:
			return 0
		if nums[-1] > nums[-2]:
			return len(nums) - 1


class Solution:

	def findPeakElement(self, nums):
		for i in range(1, len(nums)):
			if nums[i] < nums[i - 1]:
				return i - 1
		return len(nums) - 1


class Solution:

	def findPeakElement(self, nums):
		n = len(nums)
		if n == 0:
			return null
		if n == 1:
			return 0
		if nums[0] > nums[1]:
			return 0
		for ind in range(1, len(nums) - 1):
			print(ind)
			if nums[ind] > nums[ind - 1] and nums[ind] > nums[ind + 1]:
				return ind
		if nums[n - 1] > nums[n - 2]:
			return n - 1


class Solution:

	def findPeakElement(self, nums):
		if len(nums) == 1:
			return 0
		(left, right) = (0, len(nums) - 1)
		length = len(nums)
		while left + 1 < right:
			mid = (left + right) // 2
			if mid == 0:
				if nums[mid] > nums[mid + 1]:
					return 0
				else:
					left = mid + 1
			elif mid == length - 1:
				if nums[-1] > nums[-2]:
					return mid
				else:
					right = mid - 1
			elif nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
				return mid
			elif nums[mid] < nums[mid - 1] and nums[mid] < nums[mid + 1]:
				right = mid - 1
			elif nums[mid] > nums[mid + 1]:
				right = mid - 1
			else:
				left = mid + 1
		for idx in range(left, right + 1):
			if idx == 0 and nums[idx] > nums[idx + 1]:
				return 0
			if idx == length - 1 and nums[-1] > nums[-2]:
				return idx
			if nums[idx] > nums[idx - 1] and nums[idx] > nums[idx + 1]:
				return idx


class Solution:

	def findPeakElement(self, nums):
		length = len(nums)
		if length == 0:
			return None
		if length == 1:
			return 0
		if length == 2:
			return 0 if nums[0] > nums[1] else 1
		for idx in range(0, length):
			value = nums[idx]
			if idx > 0 and idx < length - 1 and (nums[idx + 1] < value) and (nums[idx - 1] < value):
				pick = idx
			elif idx == 0 and nums[idx + 1] < value:
				pick = idx
			elif idx == length - 1 and nums[idx - 1] < value:
				pick = idx
		return pick


class Solution:

	def findPeakElement(self, nums):
		if len(nums) == 0 or len(nums) == 1:
			return 0
		(l, r) = (0, len(nums))
		while l < r:
			if l == r:
				break
			m = (l + r) // 2
			if m < len(nums) - 1 and nums[m] > nums[m + 1]:
				if nums[m] >= nums[m - 1]:
					return m
			if m < len(nums) - 1 and nums[m] < nums[m + 1] and (nums[m - 1] < nums[m]):
				l = m + 1
			else:
				r = m
		if l > 0:
			if nums[l] > nums[l - 1]:
				return l
			else:
				return l - 1
		elif nums[l] > nums[l + 1]:
			return l
		else:
			return l + 1


class Solution:

	def findPeakElement(self, nums):
		return self.helper(nums, 0, len(nums) - 1)

	def helper(self, nums, start, end):
		if start == end:
			return start
		mid = (end + start) // 2
		if nums[mid] > nums[mid + 1]:
			return self.helper(nums, start, mid)
		else:
			return self.helper(nums, mid + 1, end)


class Solution:

	def findPeakElement(self, nums):

		def bs(nums, i, j):
			if i >= j:
				return j
			k = (i + j) // 2
			if nums[k] < nums[k + 1]:
				return bs(nums, k + 1, j)
			else:
				return bs(nums, i, k)
		if not nums:
			return None
		return bs(nums, 0, len(nums) - 1)