How do i find a value in an array in the most efficient way in that case?

Question

NOTE: this algorithm should be done in the most efficient way that's a bad idea to have O(n^2)

This is a two dimensional array, now notice it's hard to see that in first glance but there is a hidden pattern on that array.

this array is actually sorted take a look at that image below you may see the pattern now.

the goal here is to make a function that searches for a value in an array that follows the exact pattern like the array i've showed you in the image and you need to return true if the value was found and also print the column and row where the value sits in the array. if value wasn't found return false

here is an example

here is the function signature

public static boolean search(int [][]mat,int num){
    //Code Here
}

let's say we are looking for the value 22 in that array(the same array in the image)

int [][]arr= {{1,3,7,9},{6,4,15,11},{36,50,21,22},{60,55,30,26}}
search(arr,22); //Returns true and also will be printed "row = 2 col = 3"

search(arr,86); //Returns false

Answer 1

The indices i and j into your matrix can be computed from a single linear index ranging from 0 through 15. This will allow you to do a normal binary search just translating each index from 1D to 2D.

private static int i(int index) {
    return iBit(index / 4) * 2 + iBit(index % 4);
}

private static int iBit(int part) {
    return (part / 2) ^ (part % 2);
}

private static int j(int index) {
    int temp = index / 2;
    return temp / 4 * 2 + temp % 2;
}

It’s a bit tricky. So let’s check that the methods work:

    for (int index = 0; index < 16; index++) {
        System.out.format("%2d -> %d %d%n", index, i(index), j(index));
    }

Output:

 0 -> 0 0
 1 -> 1 0
 2 -> 1 1
 3 -> 0 1
 4 -> 2 0
 5 -> 3 0
 6 -> 3 1
 7 -> 2 1
 8 -> 2 2
 9 -> 3 2
10 -> 3 3
11 -> 2 3
12 -> 0 2
13 -> 1 2
14 -> 1 3
15 -> 0 3

The numbers agree with the pattern in the question.

NOTE: this algorithm should be done in the most efficient way that's a bad idea to have O(n^2)

It’s really nonsense. Big-O is defined based on the behaviour as the input size grows towards infinity. 16 does not grow towards infinty. Nor does 4. When the matrix size is constant, even a simple linear search will be O(1).