Фиксированная точка (значение, равное индексу) в заданном массиве с использованием линейного поиска — логический вопрос

Может ли кто-нибудь объяснить, почему использование этого метода ниже возвращает только первое совпадающее значение в массиве? Например, если элемент моего массива равен 0, 1, 2, 3 и 4. Он вернет 0 вместо 4. Каждое значение в массиве соответствует его индексу 4, следует использовать цикл for, возвращающий 4 после завершения последней итерации. ?

static int linearSearch(int arr[], int n) 
    { 
        int i; 
        for(i = 0; i < n; i++) 
        { 
            if(arr[i] == i) 
                return i; 
        } 
        
        /* If no fixed point present  
           then return -1 */
        return -1; 
    } 
    //main function

java arrays algorithm linear-search
person Donita0937    schedule 06.08.2020    source источник
comment
Что вы подразумеваете под фиксированной точкой здесь? Как вы называете этот метод? Вы сравниваете индекс с элементом массива, поэтому, когда они совпадают, он возвращает этот индекс. В приведенном вами примере для i = 0 сравнение arr[0] == 0 будет истинным, и оно вернет i, т.е. 0.   -  person Hitesh A. Bosamiya    schedule 06.08.2020

Ответы (3)


arrow_upward
2
arrow_downward

Это потому, что в вашем if вы сразу же вызываете return, а ваш метод должен возвращать один int. Если вы хотите собрать все фиксированные точки, вы можете изменить свой метод следующим образом:

static List<Integer> linearSearch(int arr[], int n)
{
    List<Integer> fixedPoints = new ArrayList<>();
    for(int i = 0; i < n; i++)
    {
        if(arr[i] == i)
            fixedPoints.add(i);
    }

    return fixedPoints;
}
person Andrew Vershinin    schedule 06.08.2020
comment
Привет. Что, если я хочу просто вернуть последнее совпадающее значение в массиве? - person Donita0937; 06.08.2020
comment
Затем тот же код, что и у вас, просто измените направление цикла: for(int i = n - 1; i >= 0; i--) - person Andrew Vershinin; 06.08.2020

arrow_upward
2
arrow_downward

Это вернет 4, поскольку у него есть обновленный индекс для каждого i, соответствующего его значению в массиве.

static int linearSearch(int arr[], int n) 
    { 
        int i,index = -1; 
        for(i = 0; i < n; i++) 
        { 
            if(arr[i] == i) 
                index = i; 
        } 
        
        /* If no fixed point present  
           then return -1 */
        return index; 
    } 
    //main function
person Yash Shah    schedule 06.08.2020

arrow_upward
1
arrow_downward

В: Может ли кто-нибудь объяснить, почему использование этого метода ниже возвращает только первое совпадающее значение в массиве?

Метод возвращается к коду, который его вызвал, когда достигает оператора return.

Из документа:

Возврат значения из метода

Метод возвращается к коду, который его вызвал, когда он

  • завершает все операторы в методе,
  • достигает оператора возврата, или
  • выдает исключение,

в зависимости от того, что произойдет первым.

Оператор if(arr[i] == i) возвращает true на первом шаге цикла for:

i=0
arr[0]=0

Затем выполняется строка return i;.

Q: Каждое значение в массиве соответствует его индексу 4. Должен ли цикл for возвращать 4 после завершения последней итерации?

В этом случае последняя итерация является первой итерацией цикла for. Работает только для i=0. Значение i никогда не достигает 4.

person Hülya    schedule 06.08.2020