CODEWITHSUNDEEP
javaalgorithmbinary-search
D_R
D_R

Reputation: 4972

Find a number in sorted multidimentional array with binary search

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.

Upvotes: 4

Views: 6217

Answers (10)

Vikram Bhat
Vikram Bhat

Reputation: 6246

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].

Upvotes: 1

Vivin Paliath
Vivin Paliath

Reputation: 95588

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.

Upvotes: 5

user3076574
user3076574

Reputation: 161

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.

Upvotes: 0

René Link
René Link

Reputation: 51473

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]

Upvotes: 1

user987339
user987339

Reputation: 10727

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

Upvotes: 0

Tareq Salah
Tareq Salah

Reputation: 3718

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

Upvotes: 0

Ted Bigham
Ted Bigham

Reputation: 4348

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.

Upvotes: 0

oli206
oli206

Reputation: 453

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.

Upvotes: 0

Ruchira Gayan Ranaweera
Ruchira Gayan Ranaweera

Reputation: 35587

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");
    }

Upvotes: 0

Balduz
Balduz

Reputation: 3570

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.

Upvotes: 2

Related Questions