如何使用 C# 在逐行和逐列递增的矩阵中进行搜索?
csharpserver side programmingprogramming更新于 2025/6/28 5:07:17
此问题的基本解决方案是扫描输入矩阵中存储的所有元素以搜索给定的键。如果矩阵的大小为 MxN，则此线性搜索方法的耗时为 O(MN)。
该矩阵可以视为一个已排序的一维数组。如果输入矩阵中的所有行按自上而下的顺序连接起来，则形成一个已排序的一维数组。在这种情况下，二分搜索算法适用于此二维数组。以下代码开发了一个 SearchRowwiseColumnWiseMatrix 函数，该函数以二维数组和搜索键作为输入，并根据搜索键是否成功返回 true 或 false。
示例
public class Matrix{
public bool SearchRowwiseColumnWiseMatrix(int[,] mat, int searchElement){
int col = getMatrixColSize(mat);
int start = 0;
int last = mat.Length - 1;
while (start <= last){
int mid = start + (last - start) / 2;
int mid_element = mat[mid / col, mid % col];
if (searchElement == mid_element){
return true;
}
else if (searchElement < mid_element){
last = mid - 1;
}
else{
start = mid + 1;
}
}
return false;
}
private int getMatrixRowSize(int[,] mat){
return mat.GetLength(0);
}
private int getMatrixColSize(int[,] mat){
return mat.GetLength(1);
}
}
static void Main(string[] args){
Matrix m = new Matrix();
int[,] mat = new int[3, 4] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
Console.WriteLine(m.SearchRowwiseColumnWiseMatrix(mat, 11));
}
输出
TRUE
