我怎样才能解决这个递归

Question

这段代码是找到一个整数数组的峰值数 问题是我得到一个错误Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 7。

public long DivideAndConquer(int lo,int hi) 
{ 
    int mid=((lo+hi)-1)/2; 
    if(myarray[mid]>=myarray[mid-1]&&myarray[mid]>= myarray[mid+1]) 
    return myarray[mid]; 
    else if (myarray[mid-1]>= myarray[mid]) 
    return DivideAndConquer(lo,mid-1); 
    else if (myarray[mid]<=myarray[mid+1]) 
    return DivideAndConquer(mid+1,hi); 
return 99; 

} 

峰值数是比他们的邻居更大，如果我在数组的末尾或者在随后开始的时候我只有去寻找预览元素。

我想我得到这个错误，因为如果我的元素在最后的位置比预览大，那么是一个高峰。例如我的最后一个位置是9，那么我有myarray[9] > myarray[8]然后是一个高峰，但在第一个if语句看起来也是myarray[9+1]，我没有，所以它给了我这个错误。

我无法删除第一条语句的&&并添加“或”（||），因为那时我得到了错误的答案。请有任何想法吗？

Answer 1

不考虑算法的正确性，我来到了索引以下更改安全：

public long DivideAndConquer(int lo,int hi) 
{ 
    int mid=(lo+hi)/2; // Valid range 
    if((lo<mid||myarray[mid]>=myarray[mid-1]) 
       &&(hi>mid||myarray[mid]>= myarray[mid+1])) 
     return myarray[mid]; 
    else if (lo<mid&&yarray[mid-1]>= myarray[mid]) 
     return DivideAndConquer(lo,mid-1); 
    else if (hi>mid&&myarray[mid]<=myarray[mid+1]) 
     return DivideAndConquer(mid+1,hi); 
    return 99; 
} 

Answer 2

当你“的if-else-如果 - ”实现这样的decicision级联像...建设必须确保每个案件都得到处理。

此外，你必须确保任何计算数组索引对给定数组有效。这个要求可能会引入更多的“if”语句。

在你的文本中，你写了“如果我在数组的末尾或开头”，但在你的代码中没有检查这些条件的“if语句”。

Answer 3

就像你说的那样，问题在于当mid是数组中的最后一项时，您的实现尝试查看索引mid + 1。你需要处理这种情况。像下面这样：

public long DivideAndConquer(int lo,int hi){ 
    int mid = (lo+hi)/2; //Modified to select the middle item 
    if(mid + 1 >= myarray.length){ 
     //TODO: Handle the case when mid is the index of the last item in the array 
    } else if(mid - 1 < 0){ 
     //TODO: Handle the case when mid is the index of the first item in the array 
    } else if(myarray[mid]>=myarray[mid-1]&&myarray[mid]>= myarray[mid+1]){ 
     return myarray[mid]; 
    } else if (myarray[mid-1]>= myarray[mid]){ 
     return DivideAndConquer(lo,mid-1); 
    } else if (myarray[mid]<=myarray[mid+1]){ 
     return DivideAndConquer(mid+1,hi);' 
    } 
    return Long.MIN_VALUE; //Probably a more suitable error indicator than 99 
    //Alternatively, an exception could be thrown 
} 

如果使用上面的方法建议，实施的mid - 1 < 0和mid + 1 >= myarray.length案件处理时要特别小心。当myarray.length仅为1或2时，您可能需要对案例进行一些特殊处理。