A 4×4 globally-sorted matrix. Target = 11. You know binary search. When you see a matrix of sorted rows, what is the first thing you reach for? Each row is a sorted array of length 4, so binary search on one row costs log2(4) = 2 comparisons. Four rows means 8 comparisons total.
But this is a globally-sorted matrix — every row's last element is smaller than the next row's first. Does per-row binary search exploit that structure? Or does it pay the same price regardless?
A 4×4 globally-sorted matrix. Target = 11. You already know binary search — apply it ROW BY ROW. Each row is a sorted array of length 4; binary search on one row takes log2(4) = 2 comparisons.
Before you run anything — imagine checking a 10,000-employee directory sorted by ID. You would not start at row 0 and scan every row. But naive per-row binary search does exactly that: row 0 starts at 1, so it cannot possibly contain 11 — yet the algorithm enters it anyway, pays 2 comparisons to confirm the miss, and moves on to row 1. The structure of the matrix is invisible to it. How many rows does it enter?
After running per-row binary search on this 4×4 matrix with target 11, which rows will the search actually enter?