本文涉及的基础知识点

二分查找算法合集

题目

给你一个 山脉数组 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() - 会返回该数组的长度

分析

分三步。

代码

核心代码

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);
}
};