Giải pháp ban đầu cho vấn đề này là quét tất cả các phần tử được lưu trữ trong ma trận đầu vào để tìm kiếm khóa đã cho. Phương pháp tiếp cận tìm kiếm tuyến tính này tốn O (MN) thời gian nếu kích thước của ma trận là MxN.
Ma trận có thể được xem như một mảng một chiều đã được sắp xếp. Nếu tất cả các hàng trong ma trận đầu vào được nối theo thứ tự từ trên xuống, nó tạo thành mảng một chiều được sắp xếp. Và, trong trường hợp đó, thuật toán tìm kiếm nhị phân phù hợp với mảng 2D này. Đoạn mã dưới đây phát triển một hàm SearchRowwiseColumnWiseMatrix lấy mảng hai chiều và khóa tìm kiếm làm đầu vào và trả về true hoặc false tùy thuộc vào sự thành công hay thất bại của khóa tìm kiếm được tìm thấy.
Ví dụ
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));
} Đầu ra
TRUE