Five tasks.

---

1. ExactFind(items []Item, title string, c *metrics.Counter) (int, bool)

An exact-match search built on LowerBound.

How many extra comparisons does it need? And why can you not go the other way — build LowerBound out of an exact-match search?

---

2. UpperBound(items []Item, title string, c *metrics.Counter) int

Returns the index one past the last matching item.

With LowerBound and UpperBound, count how many times a title occurs in O(log n). Check it against algo gen -dup-rate 0.3.

---

3. Break the search four ways

Make four copies of LowerBound, each with one mistake:

• hi := len(items) - 1
• lo = mid instead of lo = mid + 1
• hi = mid - 1 instead of hi = mid
• for lo <= hi instead of for lo < hi

Run step 3's test against each and record which case caught it. Which mistake causes an infinite loop?

---

4. Find your crossover precisely

algo sweep uses fixed sizes. Write Crossover() int that narrows the range itself and returns the smallest n at which binary is faster.

Run it five times. Do you get the same number? If not, what does that tell you about the precision of the measurement?

---

5. Predictability

Step 5 claims the linear scan is partly fast because the processor predicts its jumps.

Design a measurement that shows this: the same linear search, the same comparisons, but in an unpredictable order.

(Hint: walk the array by a random permutation of indices instead of in order. The comparison count will not change.)