Как я могу решить эту рекурсию

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

При реализации такой decicision каскад, как в вашем «если-то еще, если -» ... строительство нужно следить за тем, чтобы каждый случай обрабатывался.

Также вы должны убедиться, что любой рассчитанный индекс массива действителен для данного массива. Это требование может ввести еще несколько «if» утверждений.

В тексте вы написали «если я нахожусь в конце массива или в начале», но в вашем коде нет «if-statements», проверяющих эти условия.

Answer 3

Как вы уже сказали, проблема в том, что ваша реализация пытается посмотреть на индекс 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 < 0 и mid + 1 >= myarray.length случаев. Возможно, вам понадобится специальная обработка случаев, когда myarray.length составляет только 1 или 2.