本文涉及的基础知识点
题目
给你一个 山脉数组 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() - 会返回该数组的长度
分析
分三步。
| 寻找最后一个nums[mid-1]<nums[mid]的mid，当长度大于等于2是，mid-1是左子数组最后一个元素，mid是右子数组第一个元素，两个子数组都不为空，所以索引不会非法。 |
| 升序中寻找目标数，不一定存在 |
| 降序中寻找目标值，不一定存在 |
代码
核心代码
class Solution { public: int findInMountainArray(int target, MountainArray& mountainArr) { int iTopIndex = TopIndex(mountainArr); //左边找 { int left = 0, right = iTopIndex;//左开右闭 while (right - left > 1) { const auto mid = left + (right - left) / 2; const int midValue = mountainArr.get(mid); if (midValue == target) { return mid; } else if (midValue < target) { left = mid; } else { right = mid; } } if( mountainArr.get(left) == target) { return left; } } {//右边找 int left = iTopIndex, right = mountainArr.length();//左开右闭 while (right - left > 1) { const auto mid = left + (right - left) / 2; std::cout << mid << " "; const int midValue = mountainArr.get(mid); if (midValue == target) { return mid; } else if (midValue < target) { right = mid; } else { left = mid; } } if( mountainArr.get(left) == target) { return left; } return -1; } return iTopIndex; } int TopIndex( MountainArray& mountainArr) { int left = 0, right = mountainArr.length(); while (right - left > 1) { const auto mid = left + (right - left) / 2; if (mountainArr.get(mid - 1) < mountainArr.get(mid)) { left = mid; } else { right = mid; } } return left; } };
小幅优化后的代码
左半边寻找，可以理解为：寻找最后一个<=
右半边寻找，可以理解为：寻找最后一个>=
class Solution { public: int findInMountainArray(int target, MountainArray& mountainArr) { int iTopIndex = TopIndex(mountainArr); //左边找 { int left = 0, right = iTopIndex;//左开右闭 while (right - left > 1) { const auto mid = left + (right - left) / 2; const int midValue = mountainArr.get(mid); if (midValue <= target) { left = mid; } else { right = mid; } } if (mountainArr.get(left) == target) { return left; } } {//右边找 int left = iTopIndex, right = mountainArr.length();//左开右闭 while (right - left > 1) { const auto mid = left + (right - left) / 2; std::cout << mid << " "; const int midValue = mountainArr.get(mid); if (midValue >= target) { left = mid; } else { right = mid; } } if (mountainArr.get(left) == target) { return left; } return -1; } return iTopIndex; } int TopIndex(MountainArray& mountainArr) { int left = 0, right = mountainArr.length(); while (right - left > 1) { const auto mid = left + (right - left) / 2; if (mountainArr.get(mid - 1) < mountainArr.get(mid)) { left = mid; } else { right = mid; } } return left; } };
2022年12月旧代码
class Solution { public: int findInMountainArray(int target, MountainArray &mountainArr) { int iMaxK = FindMax(mountainArr,0, mountainArr.length()); int iLeft = FindLeft(mountainArr, 0, iMaxK + 1, target); if (-1 != iLeft) { return iLeft; } return FindRight(mountainArr, iMaxK, mountainArr.length(), target); } int FindMax( MountainArray &mountainArr, int iMin, int iMax) { if (iMax - iMin <= 1) { return iMin; } int iMid = (iMin + iMax) / 2; if (mountainArr.get(iMid - 1) < mountainArr.get(iMid)) { return FindMax(mountainArr, iMid, iMax); } return FindMax(mountainArr, iMin, iMid); } int FindLeft(MountainArray &mountainArr, int iMin, int iMax, int target) { if (iMax - iMin <= 1) { if (mountainArr.get(iMin) == target) { return iMin; } return -1; } int iMid = (iMin + iMax) / 2; const int iMidValue = mountainArr.get(iMid); if (iMidValue == target) { return iMid; } if (iMidValue < target) { return FindLeft(mountainArr, iMid, iMax,target); } return FindLeft(mountainArr, iMin, iMid, target); } int FindRight(MountainArray &mountainArr, int iMin, int iMax, int target) { if (iMax - iMin <= 1) { if (mountainArr.get(iMin) == target) { return iMin; } return -1; } int iMid = (iMin + iMax) / 2; const int iMidValue = mountainArr.get(iMid); if (iMidValue == target) { return iMid; } if (iMidValue < target) { return FindLeft(mountainArr, iMin, iMid, target); } return FindLeft(mountainArr, iMid, iMax, target); } };
