Searching for an element in a 2D array

Question

For example, given a 2D array (a matrix):

{{1, 2, 3, 4}, 
{5, 6, 7, 8}, 
{9, 10, 11, 12}}

What are the solutions to find a number, such as 6?

Here's the code I tried using binary search method:

int main(){
    int sample[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
    int target = 6;
    int lowX, highX, lowY, highY, midX, midY;

    //Note: some values are hardcoded, should not matter.
    lowX = 0;
    highX = 2;
    lowY = 0;
    highY = 3;

    if(target <= sample[0][0] || target >= sample[3 - 1][4 - 1]){
        std::cout<<"Nope";
    }

    while(lowX <= highX && lowY <= highY){
        midX = (lowX + highX)/2;
        midY = (lowY + highY)/2;

        if(target < sample[midX][midY]){
            highX = midX - 1;
            highY = midY - 1;
        }
        else if(target > sample[midX][midY]){
            lowX = highX + 1;
            lowY = highY + 1;
        }
        else {
            lowX = highX + 1;
            lowY = highY + 1;
        }
    }

    if(target == sample[midX][midY]){
        std::cout<<"Found";
    }
    else{
        std::cout<<"Nope";
    }

    return 0;
}

Is this method optimal? What are the other possible solutions?

Answer 1

Have you actually tested your code (with numbers other than 6)? Because I doubt that can work.

Firstly you have lowX = highX + 1; where it most likely should be lowX = midX + 1; (dito with Y).

And more importantly, your code only adds or subtracts one from X and Y at the same time. There is no case where X and Y are changed independently from each other, thus making it impossible to navigate the whole matrix.

I would suggest two alternative solutions:

A) Run the binary search recursivly. First search the outer array for the inner element (array) that includes the sought number, then search that array.

B) Logically map the two dimensional array to a simple array and search that, e.g. an index i on a simple array maps to the indexes x = i/4 and y = x%4 of the matrix.

Questions: What is the use case for this? If the arrays are sorted like this, why use a matrix instead of a simple array? What is the logic behind using sub-arrays like this? Do you need the location of an element, or just if it's present or not?

Answer 2

Binary search is typically the best you can do for this sort of thing, but only if you can assure that the data is ordered. You never mentioned that the data will appear presorted, but did give it as an example. If the data isn't sorted, this would be a linear search.

How well a search performs depends a lot on what data you'll be dealing with. If your 2d array will never contain duplicates I would suggest a hash table.

Answer 3

Given a matrix of size m*n; doing a two dimensional search will take, whether you try to do it at the same time or Row and column in order, O(log m + log n) steps. Which is equal to O(log (m*n)), that is the complexity of normal binary search in all elements. (which is not surprising really)

Actually if the data is stored in a 2D array like int sample[3][4], you can just cast it to a int array and do a STL binary_search on it.