山脉二分找中值

lc

lc1095

山脉数组 两次二分

先二分查找山脉数组的峰值位置

再在峰值左侧升序区间和右侧降序区间分别二分查找目标值

优先返回左侧找到的索引

/**
* // 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 binary_search(MountainArray & mountainArr, int target, int L, int R, int sign)
{
target = sign * target;
while (L <= R)
{
int mid = (L + R) >> 1;
int cur = sign * mountainArr.get(mid);
if (cur == target)
return mid;
else if (cur < target)
L = mid + 1;
else
R = mid - 1;
}
return -1;
}

int findInMountainArray(int target, MountainArray &mountainArr)
{
int L = 0, R = mountainArr.length() - 1;
while (L <= R)
{
int mid = (L + R) >> 1;
if (mountainArr.get(mid) < mountainArr.get(mid + 1))
L = mid + 1;
else
R = mid-1;
}
int peak_idx = L;
int idx = binary_search(mountainArr, target, 0, peak_idx, 1 );
if (idx != -1)
return idx;
return binary_search(mountainArr, target, peak_idx + 1, mountainArr.length() - 1, -1 );

}
};