我怎樣才能解決這個遞歸

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時，您可能需要對案例進行一些特殊處理。