Определение позиции первого вхождения ключа в отсортированном массиве

Условие

Дан упорядоченный по возрастанию массив data. Требуется реализовать алгоритм бинарного поиска, который возвращает индекс первого появления заданного значения target. Если искомый элемент отсутствует, функция должна вернуть -1.

int first(const std::vector<int> arr, int key) {
    // реализовать
}

Примеры работы функции:

• data = {1, 2, 2, 2, 3}, target = 2 → результат 1
• data = {1, 3, 5, 7}, target = 4 → результат -1

Ответ

Нужно искать нижнюю границу: первый элемент, не меньший key, и затем проверить равенство. Это даёт первое вхождение за O(log n) без прохода по дубликатам.

#include <algorithm>
#include <limits>
#include <stdexcept>
#include <vector>

int first(const std::vector<int>& arr, int key) {
    auto it = std::lower_bound(arr.begin(), arr.end(), key);
    if (it == arr.end() || *it != key) return -1;
    const auto index = it - arr.begin();
    if (index > std::numeric_limits<int>::max())
        throw std::overflow_error("index does not fit int");
    return static_cast<int>(index);
}

Предусловие — массив отсортирован по возрастанию. Пустой массив вернёт -1. Сигнатура изменена на const-ссылку: передача vector по значению в условии добавляла бы копирование O(n), сводя на нет преимущество бинарного поиска.