1095.Find in Mountain Array¶
Tags: Hard Binary Search
Links: https://leetcode.com/problems/find-in-mountain-array/
(This problem is an **interactive problem*.)*
You may recall that an array A is a mountain array if and only if:
A.length >= 3- There exists some
iwith0 < i < A.length - 1such that:A[0] < A[1] < ... A[i-1] < A[i]A[i] > A[i+1] > ... > A[A.length - 1]
Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index doesn't exist, return -1.
You can't access the mountain array directly. You may only access the array using a MountainArray interface:
MountainArray.get(k)returns the element of the array at indexk(0-indexed).MountainArray.length()returns the length of the array.
Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
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() <= 100000 <= target <= 10^90 <= mountain_arr.get(index) <= 10^9
给定的序列长度至少为3，左升右降，单峰值，初看这道题目让我联想到了洛谷-P1091 合唱队形，当然了，这两道题的求解目标都不一样，一个是找峰值，一个是用LIS（虽然也是二分），只是背景有些类似罢了。
回到这个题目，求解峰值一般分为离散和连续的两种模型。离散形式就是本题这种，连续形式可以通过洛谷-P3382 【模板】三分法来练习。总结一下不同形式下的方法：
离散形式
单纯的三分法求解即可。
连续形式
通常会给定函数的表达式，并且通常限定是单峰。在求极值的过程中，不可避免地要进行函数值的计算f(x)，通常优化的方法是秦九韶算法。
在洛谷-P3382 【模板】三分法后面的题解里，大佬们给出了很多神奇的解法，在此做个总结：
-
三分法。题目里都明确指明可以用三分法求解。
-
求导法。因为函数的表达式已经给出，函数极值对应导函数的零点，所以可以对函数进行求导，然后去求函数的零点。总结一下求函数零点的方法（可以通过LeetCode 69.Sqrt(x)做练习）：
- 二分法
- 牛顿法（依赖初值的选取，但是对LeetCode 69.Sqrt(x)并不影响）。x_{k+1} =x_{k} -\frac{f( x_{k})}{f^{'}( x_{k})}, f( x) \ =\ x^{2} -n，也涉及求导函数。
- 弦截法。《数值分析》里基本都会介绍的方法，不依赖初值，超线性收敛。
-
华罗庚优选法（黄金分割法），可以参考2005杨思雨《美，无处不在——浅谈“黄金分割”和信息学的联系》的论文，论文对很经典的取石子游戏给出了O(1)的做法。
- 模拟退火算法（可参考题解里的方法）
- 粒子群优化（Particle Swarm Optimization,PSO），又称微粒群算法（可参考题解里的方法）。
这道题因为不涉及连续形式，所以只需要用一次三分，最多两次二分即可解决。首先用三分找出峰值对应的下标，用peakPos存储，然后就是手写一个lower_bound，但是需要注意，lower_bound查找的是第一个不小于目标值的数，需要最后检查查找到的数值是否等于目标值。如果左半部分没找到，就去右半部分查找，注意右边序列是降序的。
最后来计算次数是否符合要求。数据范围是10^4，三分每次确定范围需要进行两次get，所以次数不超过2*\log_2 10^4 \approx 28，最后判定下标又增加两次，左右部分二分查找最坏情况下是左半部分没找到，相当于是对整个序列的二分，另外进行了两次判定，所以最后结果是28 + 2 + 14 + 2 = 46，在100次范围内。
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Find in Mountain Array.
Memory Usage: 7 MB, less than 100.00% of C++ online submissions for Find in Mountain Array.
/**
* // 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) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = mountainArr.length();
int left = 0, right = n - 1;
while (left < right - 1) {
int midLeft = left + ((right - left) >> 1);
int midRight = midLeft + ((right - midLeft) >> 1);
if (mountainArr.get(midLeft) > mountainArr.get(midRight))
right = midRight;
else left = midLeft;
}
int peakPos = mountainArr.get(left) > mountainArr.get(right) ? left : right;
left = 0, right = peakPos;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (mountainArr.get(mid) < target) left = mid + 1;
else right = mid;
}
if (mountainArr.get(left) == target) return left;
left = peakPos, right = n - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (mountainArr.get(mid) > target) left = mid + 1;
else right = mid;
}
return mountainArr.get(left) == target ? left : -1;
}
};