二分算法的补充说明

在上一节中我们简单介绍了二分算法，通过区分小于等于，大于或者小于，大于等于我们可以求出它们的边界值。

具体方法是先看一下要求哪里的边界值，分成两部分让如果求小于等于的右边界，我们根据条件让right=mid-1,left=mid,然后再注意一下当left和right相邻的细节就可以完成二分查找的代码。

但是当我们遇到无序的数组，例如山峰索引的时候，我们该怎么办呢？接下来我想写一些自己的思考，我发现山峰索引和求数组边界的最大区别是数组求边界是数组是有序的，它是非严格的升序，但是山峰索引的数组不是有序的，我们二分查找算法的前提是数组有二分性，分成2段。

但是问题是顶峰既可以分给左边升序的，也可以分给右边降序的，见下图：

那么我们该怎么解决这个问题嗯？经过观察发现，写出二分算法的关键在于分成的两部分不要越界访问，就是当我们把5划分给降序数组时，我们的模型抽象出来就是这样：

我们要求的是箭头指向的数字，那么我们的条件就是不要让右边的条件左边也满足，比如这个我们的划分情况下，我们就不能写出这样的代码：

int left=0;int right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(arr[mid]>arr[mid-1])left=mid+1;
else right=mid;
}

这样代码错误的关键在于我们发现我们写出这行代码arr[mid]>arr[mid-1]我们让left=mid+1本意是当它是升序时，我们让left让右边跑，但是错误就在这里这个代码当我们的mid在5身上时，它满足了左边界的条件，导致了我们找不到要找的数字了，所以犯的错误就是让右边的条件满足了左边的条件，所以我们提出一个概念叫做，条件对应，即根据二分性，左边的条件只能满足左边，右边的条件只能满足右边，所以我们做出修改。

int left=0;int right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(arr[mid]>arr[mid+1])right=mid;
else left=mid+1;
}

改进的代码就满足了左边的部分满足左边界，右边的部分满足右边界，达成了条件的对应。

总结:二分算法不一定是必须是有序数组，只要我们发现一个数组具有二分性，把它分成两部分，写出对应的条件，左边的部分只满足左边的条件，右边的部分只满足右边的条件，如果我们要求的值在左边部分的最右边，我们这样写：left=mid;right=mid-1;如果我们要求的数字在右边部分的最左边我们这样写：left=mid+1;right=mid；我们观察我们这样写的目的是让left和right都往要求部分的部分跑，遵循这样的写法我们可以写出二分算法。