1. 題目

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

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

何為山脈數組？如果數組 A 是一個山脈數組的話，那它滿足如下條件：

• 首先，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]

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

MountainArray.get(k) - 會返回數組中索引為k 的元素（下標從 0 開始） MountainArray.length() - 會返回該數組的長度 注意： 對 MountainArray.get 發起超過 100 次調用的提交將被視為錯誤答案。示例 1： 輸入：array = [1,2,3,4,5,3,1], target = 3 輸出：2 解釋：3 在數組中出現了兩次，下標分別為 2 和 5，我們返回最小的下標 2。示例 2： 輸入：array = [0,1,2,4,2,1], target = 3 輸出：-1 解釋：3 在數組中沒有出現，返回 -1。提示：3 <= mountain_arr.length() <= 100000 <= target <= 10^90 <= mountain_arr.get(index) <= 10^9

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-in-mountain-array
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 先尋找最高點，mid，mid+1，比較兩者大小，左邊小，l = mid+1，右邊小，r = mid
• 然后先在左邊二分查找，找到了就返回，沒有的話，繼續查找右側。

/*** // 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 &mArr) {int n = mArr.length(), l = 0, r = n-1, high;int lval, rval, mid, midval, mid1, midval1;while(l < r){mid = l+((r-l)>>1);midval = mArr.get(mid);midval1 = mArr.get(mid+1);if(midval < midval1)l = mid+1;elser = mid;}high = l;l = 0; r = high;while(l <= r){mid = l+((r-l)>>1);midval = mArr.get(mid);if(midval == target)return mid;else if(midval > target)r = mid-1;elsel = mid+1;}l = high+1, r = n-1;while(l <= r){mid = l+((r-l)>>1);midval = mArr.get(mid);if(midval == target)return mid;else if(midval < target)r = mid-1;elsel = mid+1;}return -1;} };

4 ms 7.1 MB

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。