Hand-Rolled First-Greater-Or-Equal

core

Implement int first_geq(const vector<int>& a, int x) by hand (no lower_bound; in Python, no bisect_left/bisect_right from the bisect module either; JavaScript has no built-in binary search at all, so there is nothing to reach for; the drill wants a hand-written search in every language), where a is sorted in non-decreasing order (vector<int> in C++, list of ints in Python, array of numbers in JavaScript). Return the smallest index i such that a[i] >= x; return a.size() if no such index exists (every element is less than x). Use the loop invariant lo < hi with lo and hi narrowing toward the answer, moving hi = mid when a[mid] >= x and lo = mid + 1 otherwise, until lo == hi is the answer.

Example: first_geq({1, 3, 3, 5, 7}, 3) returns 1: a[1] == 3 is the first element >= 3. first_geq({1, 3, 3, 5, 7}, 4) returns 3, since a[2] == 3 < 4 but a[3] == 5 >= 4. first_geq({1, 3, 3, 5, 7}, 8) returns 5 (a.size()), since every element is smaller than 8.

Input format: each test in tests/*.in is laid out as:

Line 1: n, the array length.
Line 2: the n sorted values, space-separated. When n is 0 this line is omitted entirely.
Next line: q, the number of queries.
Next q lines: one integer x per line, a first_geq(a, x) query.

Test 05.in reads:

This is the empty-array edge case: n = 0, so the values line is missing and the 3 on the second line is already the query count, followed by the three queries 0, -5, 100.

Where you'll use it:

✦ Solution & editorial unlock with the pass.