1. Идея

Дан массив из n различных чисел, уже отсортированный по возрастанию. Нужно найти число q и вывести его позицию в массиве, считая с 1. Если такого числа нет, вывести -1.

Так как массив отсортирован, полный перебор не нужен. Гораздо эффективнее применить двоичный поиск.

Смысл двоичного поиска такой:

• смотрим на середину текущего отрезка;
• если в середине стоит q, ответ найден;
• если середина меньше q, то искать нужно только справа;
• если середина больше q, то искать нужно только слева.

На каждом шаге область поиска уменьшается примерно в 2 раза.

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

1. Массив отсортирован по возрастанию. Это главное условие, которое позволяет использовать двоичный поиск.

2. Все элементы различны. Значит, если a[m] == q, то это единственная подходящая позиция.

3. Нужно вывести номер записи с единицы. Но в массивах индексация обычно с нуля, поэтому при ответе выводим m + 1.

4. Если после двоичного поиска число не найдено, значит его в массиве нет, и нужно вывести -1.

3. Алгоритм

Пусть l — левая граница поиска, r — правая.

1. Считываем n, q и массив a.
2. Инициализируем:
   • l = 0
   • r = n - 1
3. Пока l <= r:
   • находим середину: m = (l + r) // 2
   • если a[m] == q, выводим m + 1 и заканчиваем программу;
   • если a[m] < q, значит q может быть только правее, делаем l = m + 1;
   • иначе a[m] > q, значит q может быть только левее, делаем r = m - 1.
4. Если цикл завершился и число не найдено, выводим -1.

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

Поддерживается такой инвариант: если число q вообще есть в массиве, то на каждом шаге оно обязательно находится внутри текущего отрезка от l до r.

Почему можно отбрасывать половину массива?

• Если a[m] < q, то все элементы слева от m и сам a[m] тоже меньше q, потому что массив отсортирован. Значит, там ответа быть не может.
• Если a[m] > q, то все элементы справа от m и сам a[m] больше q. Значит, там ответа быть не может.
• Если a[m] == q, ответ найден.

Таким образом, на каждом шаге мы не теряем возможный ответ, а только отбрасываем часть массива, где ответа точно нет.

Когда l > r, область поиска становится пустой. Это означает, что число q в массиве отсутствует, поэтому правильно вывести -1.

5. Сложность

На каждом шаге длина отрезка поиска уменьшается примерно вдвое.

• Время работы: O(log n)
• Память: O(1) дополнительной памяти, не считая самого массива

Это хорошо подходит для ограничения n до 2 * 10^5.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

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

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

    int l = 0, r = n - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] == q) {
            cout << m + 1 << "\n";
            return 0;
        } else if (a[m] < q) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

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

7. Код на Python 3

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

l = 0
r = n - 1

while l <= r:
    m = (l + r) // 2
    if a[m] == q:
        print(m + 1)
        break
    elif a[m] < q:
        l = m + 1
    else:
        r = m - 1
else:
    print(-1)