Find a number in sorted multidimentional array with binary search

Question

we got an increasing sorted multidimensional array for example:

int[][] mat = {{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16}};

How can I use binary search to find a specific number? let's say im looking for 3.

Answer 1

You can do this by translating the one-dimensional index into its two-dimensional counterpart. For example, index 0 maps to 0, 0, but index 4 will map to 1, 0, and index 15 will map to 3, 3.

This way you can use the standard binary-search algorithm, and all you have to do is to invoke the translation function when you need to look up the value at that particular index.

The formula to translate the one-dimensional index into its two-dimensional counterpart would be:

row = floor(index / columns);
column = index % columns;

This assumes that each array is sorted and that when flattened, the resulting array is also sorted.

Answer 2

If the multidimensional array is sorted, you could divide the binary search algorithm in two parts. First of all, you would perform the binary search to find the array inside the multidimensional one which contains the number you are looking for. And then, you perform the search inside that array.

Hope that helps.