题意:给定一个MountainArray(定义见题目),找到其中最早出现的target值的下标。
MountainArray.get() 函数调用不能超过100次。
解法:首先使用Binary Search找到mountain的peak,将array分为一个严格递增和一个严格递减的array,然后使用Binary Search。
class Solution{public: int find_peak(MountainArray &mountainArr) { int l=0, r=mountainArr.length()-1; while(l<=r) { int m=(l+r)/2; int m_val=mountainArr.get(m); int m_r_val=mountainArr.get(m+1); if(m_val=target) while(l<=r) { int m=(l+r)/2; int val=mountainArr.get(m); if(val==target) return m; else if(val =target) while(l<=r) { int m=(l+r)/2; int val=mountainArr.get(m); if(val==target) return m; else if(val