I believe you’ve read the section on time complexity. If not, please review it, as it’s crucial to understand why I’m opting to use binary search in a 2D array.
The logic behind searching in a 2D matrix is simple when you’re familiar with binary search. I’m going to employ a two-way search approach, considering both rows and columns. For instance, let’s say I have two variables, ‘i’ representing rows and ‘j’ representing columns. To search, I increment ‘i’ and decrement ‘j’ simultaneously. Then, I add a condition: if ‘i’ and ‘j’ point to a value equal to our target value, return true. otherwise, we continue looping. If the loop concludes without finding the target value, we return false, indicating it’s not present in the 2D matrix. Refer to the illustration below for a clearer understanding.
Additionally, it’s crucial to check each iteration: if the value of ‘i’ and ‘j’ is greater than the target value, we decrement ‘j’ to continue searching within the column. Conversely, if our target value is less than the value at ‘i’ and ‘j’, we increment the row value, denoted by ‘i++’. You can observe this behavior in the illustration provided alongside each iteration. target value was 6 in above animation.
If you find this explanation challenging, perhaps starting from a beginner level would be beneficial. Feel free to explore the ‘Beginner’ and ‘Array’ pages, where I’ve explained basic logic from scratch.
Program To Search In a 2D Matrix
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
int[,] matrix = new int[,] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 },{ 9, 10, 11, 12} };
int target = 6;
bool HasTargetNumber = FindNumberInSortedMatrix(matrix,target);
Console.WriteLine(HasTargetNumber);
}
private static bool FindNumberInSortedMatrix(int[,] matrix, int target)
{
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);
int i = 0;
int j = cols – 1;
while (i < rows && j >= 0)
{
if (matrix[i, j] == target)
{
return true;
}
else if (matrix[i, j] > target)
{
j–; // Move left in the current row
}
else
{
i++; // Move down to the next row
}
}
return false;
}
}
