Exploring a possible solution

Now that we see how inefficient it can be to scan a large 2D table cell by cell, we need a smarter way to search for a score. The key to improving performance lies in leveraging the table’s partial sorting. The table only needs to satisfy a single condition.

• The table should be sorted in rows and columns, meaning each row and each column is sorted in ascending order.

Staircase search

Staircase search is an efficient technique for searching partially sorted two-dimensional grids, where each row and each column is sorted in ascending order. Still, the matrix does not meet the stricter conditions required for 2D binary search. Instead of relying on global ordering, staircase search leverages local ordering within rows and columns to systematically narrow the search region.