Разбор задачи «Позиция элемента»

1. Идея

Нужно найти любой индекс элемента массива, равного x.

Так как массив никак не отсортирован и про него не сказано ничего дополнительного, самый естественный способ — просто пройти по всем элементам слева направо и проверить, равен ли текущий элемент числу x.

• Если нашли, сразу выводим его номер.
• Если дошли до конца и не нашли, выводим -1.

2. Наблюдения

1. Нумерация в задаче начинается с 1, а в большинстве языков программирования массивы индексируются с 0. Поэтому если элемент найден на позиции i в массиве, ответом будет i + 1.

2. Если подходящих позиций несколько, можно вывести любую. Значит, достаточно найти первую попавшуюся.

3. Ограничение n <= 2 * 10^5 спокойно позволяет обычный линейный проход по массиву за O(n).

4. Никакие сложные структуры данных не нужны:

   • сортировать массив нельзя, потому что тогда потеряется исходная позиция;
   • бинарный поиск невозможен, так как массив не отсортирован;
   • достаточно обычного перебора.

3. Алгоритм

1. Считываем n и x.
2. Считываем массив a из n чисел.
3. Проходим по массиву индексом i от 0 до n - 1.
4. Если a[i] == x, выводим i + 1 и завершаем программу.
5. Если цикл закончился без нахождения элемента, выводим -1.

4. Почему это работает

Мы проверяем каждый элемент массива.

• Если в массиве существует хотя бы один элемент, равный x, то в какой-то момент цикл дойдёт до него. Тогда программа выведет его номер ячейки.
• Если ни один элемент не равен x, то ни одно условие a[i] == x не выполнится, и после завершения цикла будет выведено -1.

Так как проверяются все возможные позиции, алгоритм не может пропустить нужный элемент. Значит, он всегда выдаёт корректный ответ.

5. Сложность

• Время: O(n), потому что в худшем случае нужно просмотреть весь массив.
• Память: O(n) на хранение массива.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    long long x;
    cin >> n >> x;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        if (a[i] == x) {
            cout << i + 1 << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
    return 0;
}

7. Код на Python 3

n, x = map(int, input().split())
a = list(map(int, input().split()))

answer = -1
for i in range(n):
    if a[i] == x:
        answer = i + 1
        break

print(answer)