一魚多吃 用 二分搜尋的觀念，來尋找絕對最大值 Peak Index in Mountain_Leetcode #852

Samuel Scrimshaw on Unsplash

這題題目在這裡:

Peak Index in a Mountain Array - LeetCode

題目會給定一個陣列，陣列裡面的元素分布就像一座山峰。

最大值的左邊都是上坡段，最大值的右邊都是下坡段。

要求我們找出陣列裡面的絕對極大值(absolute max value)所在的陣列索引

也就是說當下這個元素，大於左邊鄰居的元素值，也大於右邊鄰居的元素值。

nums[i] > nums[i-1] > ... > nums[0] 且

nums[i] > nums[i+1] > ... > nums[n-1]

答案只會有一組解。

測試範例:

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [0,2,1,0]
Output: 1

Example 3:

Input: arr = [0,10,5,2]
Output: 1

約束條件:

Constraints:

• 3 <= arr.length <= 105
• 0 <= arr[i] <= 106
• arr is guaranteed to be a mountain array.

演算法:

先回顧一個基本性質，在已經排序好的陣列元素裡面搜尋，適合使用二分搜尋法。

基本上和前一題用到的都是同樣的觀念，和鄰居去比較，
每次判斷是上坡還是下坡，去決定搜尋的方向。

假如現在是上坡，絕對最大值肯定在我的右邊。

假如現在是下坡，絕對最大值肯定在我的左邊。

程式碼:

class Solution:
　def peakIndexInMountainArray(self, arr: List[int]) -> int:
　　
　　
　　def helper(nums, left, right):
　　
　　　if left == right:
　　　　# base case:
　　　　return left
　　　
　　　mid = ( left + right ) // 2
　　　
　　　# general case
　　　if nums[mid] > nums[mid+1]:
　　　　# peak is either nums[mid] or on the left hand side
　　　　return helper(nums, left, mid)
　　　else:
　　　　# peak is either nums[mid+1] or on the right hand side
　　　　return helper(nums, mid+1, right)
　　　

　　　
　　return helper( arr, 0 , len(arr)-1)

時間複雜度:

O( log n ) : 每次都能淘汰一半不可能的區間，最多花費O( log n )次可以找到絕對最大值，也就是山峰。

空間複雜度:

O( log n ): 遞迴stack深度最大為O( log n )，最多花費O( log n )層可以抵達終止條件。

這題學完，記得去複習經典的Binary search、Search a 2D Matrix、Sqrt(x)、
Find Peak Element，背後的二分搜尋法原理和對半切從中心點去逼近解答、目標值的想法都是相通的喔!

Reference:

[1] Peak Index in a Mountain Array - LeetCode