Tìm kiếm trong mảng 2D

Bài học 11 trên 26 trong khóa học Mảng trong C++ của Coddy.

Việc tìm kiếm trong mảng 2 chiều hoặc ma trận tương tự như tìm kiếm trong mảng 1 chiều. Ta phải duyệt qua từng phần tử. Nếu phần tử đó có trong ma trận, ta phải trả về true, nếu không thì trả về false.

Dùng các vòng lặp lồng nhau để duyệt bằng các biến i và j

for(int i=0;i<m;i++){
  for(int j=0;j<n;j++){
    if(arr[i][j]==key){
      return true;
    }
  }
}
return false;

Phân tích độ phức tạp thời gian

Vì ta dùng một vòng lặp bên trong một vòng lặp khác, nên phải duyệt qua n phần tử n lần, khiến độ phức tạp là O(n²).

Thử thách

Cho ma trận cùng số hàng và số cột, hãy in bình phương của các phần tử có tổng chỉ số là số chẵn.

Ví dụ: arr[1][3], khi đó 1+3=4 là số chẵn, vậy hãy bình phương phần tử đó và in các phần tử còn lại như cũ.

Tự làm thử

#include<iostream>
using namespace std;


int main(){
  
  int m,n;
  cin>>m>>n;

for(int i=0;i<m;i++){
  for(int j=0;j<n;j++){
    
    cin>>arr[i][j];
    
  }
}


//Code here




return 0;

}