วิธีแก้ปัญหาเบื้องต้นสำหรับปัญหานี้คือการสแกนองค์ประกอบทั้งหมดที่จัดเก็บไว้ในเมทริกซ์อินพุตเพื่อค้นหาคีย์ที่ระบุ วิธีค้นหาเชิงเส้นนี้ใช้เวลา O(MN) หากขนาดของเมทริกซ์คือ MxN
เมทริกซ์สามารถดูเป็นอาร์เรย์หนึ่งมิติที่เรียงลำดับได้ หากแถวทั้งหมดในเมทริกซ์อินพุตถูกต่อกันในลำดับจากบนลงล่าง จะสร้างอาร์เรย์แบบหนึ่งมิติที่จัดเรียงแล้ว และในกรณีนั้น อัลกอริธึมการค้นหาแบบไบนารีเหมาะสำหรับอาร์เรย์ 2 มิตินี้ โค้ดด้านล่างพัฒนาฟังก์ชัน 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
