写在前面
最近在练工作室的每日一题，目前正在二分查找阶段。其中第五天出的题是一道二分查找的综合题，他结合了前几天的知识点一起考察。LeetCode官方给这道题的TAG是困难。本人一开始看着觉得其实也不难，思路很明确，但是解题过程却很坎坷，基础不牢地动山摇，特此写一篇博客记录一下。
题目
给你一个山脉数组 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]。
思路
解题思路很简单。
- 首先找到山脉的山峰元素下标，以此分割左山峰（单调递增）和右山峰（单调递减）
分割完毕后，先对左山峰进行二分查找target
- 如果左山峰查找成功，那么就直接返回下标index值
如果左山峰查找失败，再对右山峰进行二分查找target
- 如果右山峰查找成功，那么就直接返回下标Index值
- 如果右山峰查找失败，那么就返回-1表示查找失败
解题过程
Round 1：有问题
一开始按照上述思路进行代码编写，但是并不成功。二分的思路虽然很简单，但是真的很细节！！！
发现问题：
- Part 1中的
while循环第二个条件直接使得整个循环无法进行 - Part 1中的
while循环后的if块无任何意义。因为，既然这个是山峰数组，那么就必然能找到山峰元素。应该结合问题1，当找到山峰元素直接break出循环即可
需要注意：
- 对于找右边数组，由于右边数组是单调递减的，当
midVal > target时，midVal是在target的左边。因此，left = mid + 1。
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
//Part 1：找到山峰元素索引
int left = 0;
int right = mountainArr.length() - 1;
int topIndex = -1;
while(left <= right && topIndex != -1){ //后项判断替代return ##兄弟你有问题！！！
int mid = right + (left - right) / 2;
//减少get方法调用，用变量缓存起来
int midVal = mountainArr.get(mid);
int midMinusVal = mountainArr.get(mid - 1);
int midPlusVal = mountainArr.get(mid + 1);
//刚好命中
if(midMinusVal < midVal && midVal > midPlusVal){
topIndex = mid;
}else if(midVal < midPlusVal){ //mid在左边
left = mid + 1;
}else{ //mid在右边
right = mid - 1;
}
}
if(topIndex == -1){ //##兄弟你有问题！！！
topIndex = left; //##兄弟你有问题！！！
} //##兄弟你有问题！！！
//Part 2：先找左边数组，左边数组有就结束，没有就继续到Part 3找右边数组
left = 0;
right = topIndex;
while(left <= right){
int mid = right + (left - right) / 2;
int midVal = mountainArr.get(mid);
if(midVal == target){
return mid; //左边数组有，且直接命中，结束
}else if(midVal > target){
right = mid - 1;
}else{
left = mid + 1;
}
}
//Part 3：找右边数组，还是找不到的话返回-1
left = topIndex;
right = mountainArr.length() - 1;
while(left <= right){
int mid = right + (left - right) / 2;
int midVal = mountainArr.get(mid);
if(midVal == target){
return mid; //右边数组有，且直接命中，结束
}else if(midVal > target){
left = mid + 1; //#需要注意！！！
}else{
right = mid - 1;
}
}
//还找不到那就真的找不到了
return -1;
}
}Round 2：还是有问题
按照上面存在的问题改了下，还是不行。找山峰元素依然用的是循环中找答案的二分查找方法。
发现问题：
- 在Part 1中，存在
mid = 0的可能，如果进行mid - 1运算的话，结果是-1，会发生数组下溢（直到Round 5才解决）。
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
int left = 0;
int right = mountainArr.length() - 1;
//Part 1：找到山峰元素索引
int topIndex = -1;
while(left <= right){
int mid = left + (right - left) / 2;
//减少get方法调用，用变量缓存起来
int midVal = mountainArr.get(mid);
int midMinusVal = mountainArr.get(mid - 1); //##兄弟你有问题！！！
int midPlusVal = mountainArr.get(mid + 1);
//刚好命中
if(midMinusVal < midVal && midVal > midPlusVal){
topIndex = mid;
break;
}else if(midVal < midPlusVal){ //mid在左边
left = mid + 1;
}else{ //mid在右边
right = mid - 1;
}
}
// 后面没有问题，省略...
}
}Round 3：还是有问题，但是快可以了
在修改上述代码的时候，我一直不知道怎么解决，很是懵逼。
后来请教了Uni，说我找山峰元素有问题。然后看到他使用到了缩小可能存在区间的二分查找方法，我直接改用了也没管为什么，因为我当时实在是懵逼，不知道怎么解决。实际上，循环中找答案没有任何问题，只不过是我们需要排除存在mid = 0的可能即可。
但是按照Uni的代码修改后，还是有问题，最后发现是我自己看走眼了。
发现问题：
- 发生了
index = mountArr.length()的数组上溢。后来仔细对比，取mid元素下标的式子写成int mid = right + (left - right) / 2;，而正确应该是int mid = left + (right- left ) / 2;。前者是向下取整，后者是向后取整。如果是向下取整，当剩下只有两个元素时，mid永远等于左元素，因此mid + 1不会溢出。
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
int left = 0;
int right = mountainArr.length() - 1;
//Part 1：找到山峰元素索引
int topIndex;
while(left < right){
int mid = right + (left - right) / 2; //##兄弟你有问题！！！
if(mountainArr.get(mid) < mountainArr.get(mid + 1)){
left = mid + 1;
}else{
right = mid;
}
}
topIndex = left;
// 后面没有问题，省略...
}
}Round 4：终于解决了，但是有疑惑
通过修改成向下取整，终于解决了数组上溢的问题。注意：此时Round 2 中的数组下溢问题还没解决。
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
int left = 0;
int right = mountainArr.length() - 1;
//Part 1：找到山峰元素索引
int topIndex;
while(left < right){
int mid = left + (right - left) / 2;
if(mountainArr.get(mid) < mountainArr.get(mid + 1)){
left = mid + 1;
}else{
right = mid;
}
}
topIndex = left;
// 后面没有问题，省略...
}
}我的疑惑：
为什么在我使用同一种方法，即循环中找答案，在LeetCode 852. 山脉数组的峰顶索引中，不会发生数组下溢的问题呢？
class Solution { public int peakIndexInMountainArray(int[] arr) { int left = 0; int right = arr.length - 1; while(left <= right){ int mid = right + (left - right) / 2; //#修改 if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]){ //刚好命中 return mid; }else if(arr[mid] < arr[mid + 1]){ //在左边 left = mid + 1; }else{ //在右边 right = mid - 1; } } return left; } }
后来仔细一看，噢！我又看走眼了。在这道题我使用的是向上取整，那么mid最小值就为1，从而mid - 1 >= 0 ，就不会发生下溢了。
Round 5：大功告成
然后修改成向上取整，大功告成！循环中找答案也没毛病！
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
//Part 1：找到山峰元素索引
int left = 0;
int right = mountainArr.length() - 1;
int topIndex = -1;
while(left <= right){
int mid = right + (left - right) / 2; //right+排除了Mid为0的可能
int midVal = mountainArr.get(mid);
int midMinusVal = mountainArr.get(mid - 1);
int midPlusVal = mountainArr.get(mid + 1);
//刚好命中
if(midMinusVal < midVal && midVal > midPlusVal){
topIndex = mid;
break;
}else if(midVal < midPlusVal){ //mid在左边
left = mid + 1;
}else{ //mid在右边
right = mid - 1;
}
}
}
// 后面没有问题，省略...
}