Exploring a possible solution

Now that we understand how time-consuming it is to scan a large 2D table cell by cell, we need a smarter way to search for a score like 85. The key to improving performance lies in understanding how the table is structured.

Each row is sorted from left to right, and every row starts with a score that is greater than the last score of the previous row. This means the entire table behaves like a single, continuous, increasing sequence, just laid out in two dimensions.

2D binary search

2D binary search is an extension of the classic binary search algorithm for two-dimensional grids. Similar to standard binary search, it leverages the sorted order to efficiently locate a target value. Instead of examining each cell individually, 2D binary search repeatedly partitions the search space, eliminating regions where the target cannot possibly exist. By doing so, it reduces the number of comparisons dramatically, just like binary search halves the search space in a one-dimensional space.