Understanding 2D binary search algorithm

The strategy from the earlier example can be extended to create a 2D binary search algorithm. To explain this algorithm, we will use a 2D matrix sorted in ascending order both row-wise and column-wise, and search for a target value. For the algorithm to work, the input array should meet the two conditions below.

• The 2D matrix should be sorted in rows and columns, meaning each row and each column is sorted in ascending order.
• The last number in each row should be less than or equal to the first number in the next row.

If either of these conditions is violated, the algorithm may fail to locate the target element. This can be seen in the example below, where the input does not satisfy the required sorting conditions.

For such input, we can tweak the existing binary search algorithm to search the 2D matrix rather than using the poorly performing linear search.

Flatten the 2D matrix

We already know how to execute a binary search in a sorted array. If we flatten this 2D matrix into a 1D sorted array, we can use binary search to find the target. There are two ways to do it.