Practice: Binary Search

Twelve problems on sorted data. The first nine are the lesson's function with one line changed; write that function once, test it on the samples, and keep it. Several statements allow n = 0: then the second line is empty, the loop runs 0 times, and the answer is "not found".

• Find in Sorted Array: the lesson's function as it stands.
• First Occurrence, Last Occurrence, Count Equal Values: when a[m] == x, don't stop — remember m and keep searching to the left (first) or to the right (last). The count is last − first + 1, or 0.
• Insertion Position: the first index with a[i] >= x; when a[m] < x, move l, otherwise remember m and move r. The answer may be n + 1.
• Floor Value and Ceiling Value: the largest a[i] <= x, the smallest a[i] >= x, or NONE — the same search, remembering a value instead of an index.
• Closest Sorted Queries: the ceiling and the element just before it are the only two candidates; ties go to the smaller value and then the smaller index. Values reach 10¹⁸.
• Count in a Value Range: (first index > r) − (first index >= l), two searches per query.
• First One: a sorted row of 0s and 1s — the first 1 is the first element >= 1.
• Worms: build the running totals t[i] = worms in piles 1..i; they are increasing, so the pile of label q is the first i with t[i] >= q.
• Flattened Matrix Search: the rows joined end to end make one sorted vector of n·m values; search it, then turn the index k back into row k / m and column k % m.