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.

Answer 3

You can use Arrays.binarySearch() for each sub array.

private static int[] binarySearch2d(int[][] arr, int toFind) {
    int[] index2d = new int[] { -1, -1 };

    // find the row
    int row = -1;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i][0] > toFind) {
            break;
        }
        row = i;
    }

    if (row > -1) {
        int indexInSecond = Arrays.binarySearch(arr[row], toFind);
        if (indexInSecond > -1) {
            index2d[0] = row;
            index2d[1] = indexInSecond;
        }
    }
    return index2d;
}

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

    int[] found = binarySearch2d(mat, 12);
    int element = mat[found[0]][found[1]];
    System.out.println("Found: " + element + " at mat[" + found[0] + "]["
            + found[1] + "]");
}

will output

Found: 12 at mat[2][3]

Answer 4

2-d array can be used as 1-d array in following way using following formula for index:-

Say you need to find kth index in 1-d array then it be element with i= k/n and j = k%n where n is order of the matrix in the 2-d array. Use binary search as in 1-d array with ending index n*n-1.

Alternative Approach:-

1.> Do binary search on first elements of each 1-D array that arr[i][0].

2.> Then using above get the 1-D array which contains the element say k then do binary search on arr[k].

Answer 5

You can create an one dimensional array and use binary search .

    int[] arr = new int[]{1, 5, 6};// your converted array
    int index = Arrays.binarySearch(arr, 1);
    if (index >= 0) {
        System.out.println("found ");
    } else {
        System.out.println("not found");
    }

Answer 6

You could use the first number of each array (or the last) to find the element where your number could be present and then use binary search on that element to find if it's actually there.

Answer 7

public boolean Find(int[][] array, int number) { 
    int find = -1;
    for(int i = 0; i < N; i++) {
        find = binarySearch(array[i], number, 0, N);
        if(find != -1) { 
           return true; //the element is exist
        }
     }
     return false;//the element is not exist
}

Or you can revise this question it will help you a lot

Answer 8

You could do a binary search using just the first element of each inner array to find which row it is in. Then do a binary search inside that row to find the column.

You might need a little more logic if your matrix supports duplicates.

Answer 9

Use java.util.Arrays. Use Arrays.binarySearch() function on flattened matrix:

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


int key = 3;
int[] oneDArray = new int[mat[0].length*mat[0].length];

int s = 0;
for(int i = 0; i < mat[0].length; i ++) 
    for(int j = 0; j < mat[0].length; j ++){                           
        oneDArray[s] = mat[i][j];
        s++;
    } 


int found = Arrays.binarySearch(oneDArray, key);
if(found > -1){
     System.out.println(found/ mat[0].length + "," + found % mat[0].length);    
}

And the demo: https://ideone.com/bFZVMs

Answer 10

There are different ways to define 'order' in a two-dimensional array. For the order in your example, do bin search on the first element of each row, to find the row, and then do bin search again inside the row. if the number of rows is >= than the number of columns, you can optimize doing binary search on the elements of the diagonal that starts at (0,0), then do another binary search on the rest of the row.