二分查找能否用于“看似无序”的序列
一道LeetCode算法题奉上：
https://leetcode-cn.com/problems/find-in-mountain-array/
这道题是在说，在一个数组中，它的元素中存在一个峰值，峰值左右两边的元素都比它小，然后给出一个查找值target，让你找到元素值等于target的最小下标，如果没有就返回-1。
峰值左边的元素由小到大排列，峰值右边的元素由大到小排列，整个数组毫无疑问是无序的，但它是部分有序的，如下图所示：
如果单纯在峰值左边或是峰值右边都可以进行二分查找。可是问题来了，要如何在茫茫人海中找到峰值呢？
细心的朋友已经发现了：
如果遇到一个元素，它的左边元素比它小，右边元素比它大，那么峰值一定在它的右边；
如果遇到一个元素，它的左边元素比它大，右边元素比它小，那么峰值一定在它的左边；
如果遇到一个元素，它的左边元素比它小，右边元素也比它小，那么它就是峰值！
根据以上规律，就可以写一个二分查找峰值的算法了。
int findsummit(vector<int> arr)
{
int len=arr.size;
int left=0;
int right=len-1;
while(left<=right)
{
int mid=(left right)/2;
int pre=arr[mid-1];
int now=arr[mid];
int aft=arr[mid 1];
if(pre<now&&now>aft)
{
return mid;
}
else if(pre<now&&now<aft)
{
//峰值在右边
left=mid 1;
}
else
{
//峰值在左边
right=mid;
}
}
return -1;
}
这里与简单二分查找略有不同的是峰值如果在左边right置为mid而不是mid-1，这是为了防止数组越界，大家可以思考一下为什么，本文主要介绍二分思想就不再过多介绍了。
找到了峰值的位置（下标），我们再去找target就易如反掌了，可以直接套用简单二分查找算法的模板。既然题目要求找到等于target的元素的最小下标，我们就先找左边，即[0,summit]；再找右边，即[summit,len-1]。summit为峰值下标，len为序列长度。
以下代码为通过该题的代码：
/**
* // 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) {
int len=mountainArr.length;
int left=0;
int right=len-1;
int summit=-1;
int mid=-1;
while(left<=right)
{
mid=(left right)>>1;
int pre=mountainArr.get(mid-1);
int now=mountainArr.get(mid);
int aft=mountainArr.get(mid 1);
if(pre<now&&now>aft)
{
summit=mid;
break;
}
else if(pre<now&&now<aft)
{
left=mid 1;
}
else
{
right=mid;
}
}
left=0;
right=summit;
while(left<=right)
{
mid=(left right)>>1;
int now=mountainArr.get(mid);
if(target==now)
{
return mid;
}
else if(target<now)
{
right=mid-1;
}
else
{
left=mid 1;
}
}
left=summit;
right=len-1;
while(left<=right)
{
mid=(left right)>>1;
int now=mountainArr.get(mid);
if(target==now)
{
return mid;
}
else if(target>now)
{
right=mid-1;
}
else
{
left=mid 1;
}
}
return -1;
}
};
