Geek Answers Handbook

Find a number in a sorted multidimensional binary search array

we got an enlarged 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 search for a specific number? let them tell them to search 3.

+4
source share
10 answers

You can do this by translating the one-dimensional index into its two-dimensional copy. For example, the index is 0displayed in 0, 0, but the index 4will be displayed in 1, 0, and the index 15will be displayed in 3, 3.

, , , , , .

:

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

, .

+5

, . , , , , . .

, .

+2

Arrays.binarySearch() .

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


Found: 12 at mat[2][3]
+1

2- 1- , : -

, k- 1-, i= k/n j = k%n, n - 2-d. , 1-d n * n-1.

: -

1. > 1-D , arr[i][0].

2. > , , 1-D , say k, arr[k].

+1

array binary.

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

( ), , , , , .

0
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
}

,

0

, , , . , .

, .

0

java.util.Arrays. Arrays.binarySearch() :

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

: https://ideone.com/bFZVMs

0

There are different ways to determine the "order" in a two-dimensional array. To order in your example, search the bin for the first element of each row to find the row, and then search again in the row inside the row. if the number of rows is> = the number of columns, you can optimize the binary search for the diagonal elements that starts with (0,0), and then perform another binary search in the rest of the row.

0
source

More articles:


All Articles