Binary search code fails efficiency check

I have been tasked to complete a technical assessment for a position involving a simple C++ coding exercise. The problem was to check if a number exists in a sorted array, where:

ints[] is the array to be sorted
size is the size of the array
k is the number to be checked

The requirement was to implement a solution that uses as few CPU cycles as possible. My solution was as follows:

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;
}

This failed the performance test with a million items in the array. I am a bit confused as to why. Is it the fact that I am creating a new structure from the vector? Does it involve copying all of the items in a new location in memory?

Solution

std::vector<int> v(ints,ints+size); is going to make a copy of your array. You really don't want to do this in a binary search function since it is an O(N) operation. That totally dominates the O(logN) of a binary search and makes you algorithm equivalent to a linear search (only worse since you are also consuming O(N) space). You should be using the array directly in your call to binary_search like you do to create the vector with:

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