一魚多吃 用二分搜尋法 找目標值 Find in Mountain Array_Leetcode #1095

Kyle Johnson on Unsplash

這題的題目在這裡:

題目敘述

題目會給我們一個山形的輸入陣列，和目標值target，要求我們找出目標值所在的陣列索引。如果出現兩次，返回比較小的那一個，也就是比較靠左的那個索引值。

山形的意思就是說，從最左側到山頂最大值都是遞增，從山頂最大值到右側都是遞減。

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
• • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

測試範例

Example 1:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

Example 2:

Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.

約束條件

Constraints:

• 3 <= mountain_arr.length() <= 104
• 0 <= target <= 109
• 0 <= mountain_arr.get(index) <= 109

演算法

這題也是屬於二分搜尋法的應用題。
因為題目已經說是山形陣列，我們可以先用二分搜尋法找出最大值，也就是山頂。如同前面這題我們學過的技巧，來找山形陣列的絕對最大值。

找到山頂之後，整個陣列可以分成兩塊，左邊這塊剛好都是遞增的分布，右邊這塊剛好都是遞減的分布。不論是在左邊找，還是在右邊找，都是在已經排序好的子陣列尋找目標值，恰好符合二分搜尋法的應用場景。

接著先找左邊這塊，假如左邊這塊找不到再找右邊這塊；如果，最後還是找不到，就返回-1，代表找不到目標值。

程式碼

class Solution:
　
　def findPeak(self, mountain_arr) -> int:
　　
　　left, right = 0, mountain_arr.length()-1
　　
　　while left < right :
　　　
　　　probe = left + ( right - left ) // 2
　　　
　　　if mountain_arr.get(probe) > mountain_arr.get(probe+1):
　　　　right = probe
　　　else:
　　　　left = probe + 1
　　　　
　　return right
　
　

　def findTarget(self, mountain_arr, peak_index, target) -> int:
　　
　　# Phase_#1: Find Target in uphill
　　left, right = 0, peak_index
　　
　　while left <= right:
　　　
　　　probe = left + ( right - left ) // 2
　　　
　　　probe_value = mountain_arr.get( probe )
　　　
　　　if probe_value == target:
　　　　return probe
　　　
　　　elif probe_value < target:
　　　　left = probe+1
　　　
　　　else:
　　　　right = probe-1
　　
　　
　　# Phase_#2: Find Target in downhill
　　left, right = peak_index, ( mountain_arr.length()-1 )
　　
　　while left <= right:
　　　
　　　probe = left + ( right - left ) // 2
　　　
　　　probe_value = mountain_arr.get( probe )
　　　
　　　if probe_value == target:
　　　　return probe
　　　
　　　elif probe_value < target:
　　　　right = probe-1
　　　
　　　else:
　　　　left = probe+1
　　　　
　　return -1
　　　
　

　def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
　　
　　# Find mountain peak
　　peak_index = self.findPeak(mountain_arr)
　　
　　# Find target in up-hill,then down-hill, or target does not exist in montain
　　index_of_target = self.findTarget( mountain_arr, peak_index, target)
　　
　　return index_of_target

複雜度分析

時間複雜度: O( log n)
都是用二分搜尋法來找最大值(山頂)和目標值(target)。

T(n) = T(n/2) + O(1),

T(n) = O( log n )

空間複雜度: O(1)

所用到的都是固定的臨時變數，所占用的記憶體空間為常數級別O(1)

關鍵知識點

在已經排序好的陣列尋找目標值，聯想到二分搜尋法，這是標準的二分搜尋法的應用場景。

建議回頭複習高度關聯的題目:

Binary search, 找絕對最大值, 找相對最大值

Reference:

[1] Python O( log n ) sol. based on variant binary-search, run-time 88%+ - Find in Mountain Array - LeetCode