Sorted Array Search: std::lower_bound vs. Linear Scan

Question 5 / 51 • Correct so far: 0 (0 answered)

Snippet A

Binary Search

bool contains(const std::array<int, kTableSize>& table, int key) {
    auto it = std::lower_bound(table.begin(), table.end(), key);
    return it != table.end() && *it == key;
}

for (int q : QUERIES)
    found += contains(SORTED_TABLE, q) ? 1 : 0;
Snippet B

Linear Scan

bool contains(const std::array<int, kTableSize>& table, int key) {
    for (int v : table)
        if (v == key) return true;
    return false;
}

for (int q : QUERIES)
    found += contains(SORTED_TABLE, q) ? 1 : 0;
Shared test data (shared-setup) 
constexpr int kTableSize = 16;
constexpr int kQueries   = 65536;

static const std::array<int, kTableSize> SORTED_TABLE = {
    2, 5, 11, 17, 23, 31, 41, 53, 67, 79, 89, 97, 107, 127, 149, 163
};

static std::vector<int> makeQueries() {
    std::mt19937 rng(7);
    std::uniform_int_distribution<int> dist(0, 170);
    std::vector<int> qs(kQueries);
    for (auto& q : qs) q = dist(rng);
    return qs;
}

static const std::vector<int> QUERIES = makeQueries();

Which snippet is faster?

Select the correct answer(s)