（這是一個 交互式問題 ）

給你一個 山脈數(shù)組 mountainArr，請你返回能夠使得 mountainArr.get(index) 等于 target 最小 的下標 index 值。

如果不存在這樣的下標 index，就請返回 -1。

所謂山脈數(shù)組，即數(shù)組 A 假如是一個山脈數(shù)組的話，需要滿足如下條件：

首先，A.length >= 3

其次，在 0 < i < A.length - 1 條件下，存在 i 使得：

A[0] < A[1] < … A[i-1] < A[i]
A[i] > A[i+1] > … > A[A.length - 1]

你將 不能直接訪問該山脈數(shù)組，必須通過 MountainArray 接口來獲取數(shù)據(jù)：

MountainArray.get(k) - 會返回數(shù)組中索引為k 的元素（下標從 0 開始）
MountainArray.length() - 會返回該數(shù)組的長度

注意：

對 MountainArray.get 發(fā)起超過 100 次調(diào)用的提交將被視為錯誤答案。此外，任何試圖規(guī)避判題系統(tǒng)的解決方案都將會導(dǎo)致比賽資格被取消。

為了幫助大家更好地理解交互式問題，我們準備了一個樣例 “答案”：https://leetcode-cn.com/playground/RKhe3ave，請注意這 不是一個正確答案。

示例 1：

輸入：array = [1,2,3,4,5,3,1], target = 3
輸出：2
解釋：3 在數(shù)組中出現(xiàn)了兩次，下標分別為 2 和 5，我們返回最小的下標 2。
示例 2：

輸入：array = [0,1,2,4,2,1], target = 3
輸出：-1
解釋：3 在數(shù)組中沒有出現(xiàn)，返回 -1。

提示：

3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9
第一次見到這種題目，之前codeforces好像見到過一次交互題，也沒整明白。。
這個題其實就是一個三分+二分的題目。
三分，我們找出“山頂”。二分，先對“左山坡”二分，如果沒有找到要找的值，就對“右山坡”進行二分，找不到就是-1.三分挺久沒寫了，有點生疏，調(diào)了好久。。
代碼如下：

/*** // This is the MountainArray's API interface.* // You should not implement it, or speculate about its implementation* class MountainArray {* public:* int get(int index);* int length();* };*/ class Solution { public:int findInMountainArray(int target, MountainArray &mountainArr) {int l=0;int r=mountainArr.length()-1;int top;while(l<=r){int mid=l+(r-l)/3;int midd=r-(r-l)/3;//cout<<"**"<<l<<" "<<r<<endl;//cout<<mid<<" "<<midd<<endl;if(mountainArr.get(mid)>mountainArr.get(midd)){r=midd-1;}else l=mid+1;}//cout<<r<<endl;top=r;l=0;while(l<=r){int mid=(l+r)>>1;int x=mountainArr.get(mid);if(target==x) return (mid);else if(target>x) l=mid+1;else r=mid-1;}l=top,r=mountainArr.length()-1;while(l<=r){int mid=(l+r)>>1;int x=mountainArr.get(mid);if(x==target) return mid;else if(x<target) r=mid-1;else l=mid+1;}return -1;} };

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的1095. 山脉数组中查找目标值(三分+二分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。