Двоичный код поиска не проходит проверку эффективности

Question

Мне было поручено выполнить техническую оценку позиции, включающей простое упражнение по кодированию на C ++.Проблема состояла в том, чтобы проверить, существует ли число в отсортированном массиве, где:

• ints[] - это сортируемый массив
• size - это размер массива
• k - это проверяемое число

Требовалось внедрить решение, которое использует как можно меньше циклов ЦП.Мое решение было следующим:

static bool exists(int ints[], int size, int k)
{
    std::vector<int> v(ints,ints+size);

    if (std::binary_search (v.begin(), v.end(), k))
        return true;

    return false;
}

Это провалило тест производительности с миллионом элементов в массиве.Я немного смущен, почему.Это тот факт, что я создаю новую структуру из вектора?Включает ли это копирование всех элементов в новом месте в памяти?

Answer 1

std::vector<int> v(ints,ints+size); собирается сделать копию вашего массива.Вы действительно не хотите делать это в бинарной функции поиска, так как это операция O (N).Это полностью доминирует в O (logN) бинарного поиска и делает ваш алгоритм эквивалентным линейному поиску (только хуже, поскольку вы также потребляете пространство O (N)).Вы должны использовать массив непосредственно при вызове binary_search, как вы делаете это для создания вектора с:

static bool exists(int ints[], int size, int k)
{
    return std::binary_search(ints, ints+size, k);
}