Any ideas on How to search a 2D array quickly?

Question

I jave a 2D array like this, just like a matrix:

{{1, 2, 4, 5, 3, 6},
{8, 3, 4, 4, 5, 2},
{8, 3, 4, 2, 6, 2},
//code skips... ...

}

(The Array is not sorted) I want to get all the "4" position, instead of searching the array one by one, and return the position, how can I search it faster / more efficient? thz in advance.

Answer 1

You can't. There is no magic way. Your algorithm will always need to check each cell in your matrix, so it will always be O(n*m) for a matrix of size n * m.

If you can sort your matrix first, then you can get away with O(log(n) * m), as you can use a binary search inside each row.

Answer 2

The only way to do this is less than m * n is to have it presorted in some way. It is not clear from your question if that is possible.

Answer 3

There is no obvious algorithmic optimisation (unless you have some a priori knowledge of the data, e.g. that it's sorted, or you know how many 4s there are). However there are micro-optimisations that you can use, e.g. if your array is 32 bit int and you can use SSE then you can load and compare 4 elements at a time.

Answer 4

You can choose speed or memory consumption. If Memory is not important you could create a List of positions where values are stored. So you have still your m*n array, but additionaly an array of "position-lists". You would have to create "setter"-methods which write down a position in the lists each time a value is added or changed. So the idea is not to improve the search but avoid it.

Example:

You have a 2*2 Array.

{{0,0}
 {0,0}}

And you want to add a 4 in the . So you have to call your method write which is called with the parameters X, Y, and Value. This method would change your array to

{{4,0},
 {0,0}}

but also create a list

List4=>{(0,0)}

with the position of fours. If you add a second 4 it would look like

{{4,0}
 {4,0}}
List4=>{(0,0),(1,0)}

So if you want to find all 4 in your matrix you just have to go to all positions in your List4. Of course you would have to create a list for each value in your array. So you could have a maximum of m*n lists with positions if the matrix contains each value only once.