Searching for an element in a 2D array 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 &lt;= sample[0][0] || target &gt;= sample[3 - 1][4 - 1]){
        std::cout&lt;&lt;"Nope";
    }

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

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

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

    return 0;
}


Is this method optimal?
What are the other possible solutions?
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?