Для заданного отсортированного массива возвращает индекс i, если массив A содержит элемент A [i] такой, что A [i] = i (рекурсивно, разделяй и властвуй)

Question

Так что у меня есть домашнее задание, чтобы создать рекурсивный метод, который использует алгоритм «разделяй и властвуй» для поиска в отсортированном массиве и проверки, если A [i] == i (если значение соответствует текущему индексу массива). Теперь я не понимаю, почему мы будем использовать алгоритм «разделяй и властвуй», поскольку не искали определенного значения c.

В моей голове (я новичок) я хочу просто сделать линейный рекурсивный метод. Для массива A длиной n мы делаем ...

    if(n<0){
return -1;}

if(A[n] == n){
return n;}

else{
return recursiveMethod(Array A, n-1);
}

Так вот, как я собираюсь это сделать, но я понятия не имею, почему мы будем использовать алгоритм стиля «разделяй и властвуй». В любом случае, если бы кто-нибудь мог объяснить с точки зрения непрофессионала, так как я новичок, я был бы признателен, спасибо

Answer 1

Спасибо, что признали, что это домашнее задание :). Люди вряд ли полностью ответят за вас, но довольно часто они настолько интересны, что люди не могут избежать комментариев. Вы всегда получите лучшие ответы, если обратите внимание на такие детали, как форматирование и понятный и правильный язык. Например, ваш код было бы легче понять, если бы вы включили определение функции (function recursiveMethod(Array a, Integer start) {) и сделали отступ для тела функции.

Теперь давайте перейдем к вопросу: ваша функция требует ровно n сравнений для массив размером n (я думаю, вы уже знаете эту часть, это линейность в линейной функции , а также O (n)).

Можем ли мы добиться большего успеха?

Чтобы решить подобные вещи, попробуйте быть ленивым алгоритмом, всегда ищущим работу, которую не нужно делать. Здесь мы можем использовать тот факт, что массив отсортирован по соображениям о работе, которую мы можем пропустить: когда A[i] > i, все значения j = i..A[i] обязательно должны также удовлетворять A[j] > j. Предполагается, что A может содержать повторяющиеся значения. Если все значения в A должны быть различны, вы можете исключить немного больше, чем я делал выше ...