-2

This code is to find a peak number of an array with integer numbers The problem is that i get an error 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;

}

A peak number is a number which is bigger than their neighbors and if I am at the end of the array or at the beginning then I have to look only for the previews element.

I think I get this error because if my element in last position is bigger than previews then is a peak. For example my last position is 9 then I have myarray[9] > myarray[8] then is a peak, but in the first if statement it look also for myarray[9+1] which I don't have so it gives me this error.

I can't remove && for the first statement and add "or" (||) because then I get a wrong answer. Any ideas please?

4

3 回答 3

1

就像您说的那样,问题在于您的实现尝试查看 index mid + 1,什么时候mid是数组中的最后一项。你需要处理这种情况。类似于以下内容:

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 < 0mid + 1 >= myarray.length情况的处理时要特别小心。myarray.length当is only1或时,您可能需要对情况进行一些特殊处理2

于 2013-05-03T11:58:14.827 回答
0

当在你的“if-else-if-”中实现这样的决策级联时,必须确保每个案例都得到处理。

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

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

于 2013-05-03T11:03:08.500 回答
0

不考虑算法的正确性,为了安全索引,我做了以下更改:

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;
}
于 2013-05-03T10:57:38.657 回答