Thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++
Trong bài viết này, codehow sẽ giới thiệu đến các bạn thuật toán tìm kiếm tuyền tính (Linear Search) trong C / C++. Hay còn được gọi với cái tên khác là tìm kiếm tuần tự (sequential search).
Ví dụ: Mình có mảng Number = {2, 5, 8, 10, 22, 16, 8}. Giả sử mình muốn tìm số 5 có xuất hiện trong mảng hay không, nếu có thì nó nằm ở vị trí bao nhiêu.
Kết quả: Số 5 có xuất hiện trong mảng và nó nằm ở vị trí số 1 (vì mảng bắt đầu từ vị trí 0).
Vậy làm thế nào để viết thuật toán giải quyết vấn đề này, các bạn bắt đầu cùng mình thôi nhé.
Tìm kiếm tuyến tính là gì (Linear Search)?
Như các bạn thấy trong hình, thì để tìm được giá trị J, cần phải duyệt qua từng phần tử trước đó để tìm. Nếu danh sách chúng ta có 1000 phần tử và phần tử đó nằm ở gần cuối thì việc tìm kiếm mất rất nhiều thời gian.
Vậy thuật toán tìm kiếm tuyến tính chỉ áp dụng cho những chương trình đơn giản. Các bạn lập trình viên mới bắt đầu học thì nên tìm hiểu về thuật toán tìm kiếm này.
Nếu trong trường hợp danh sách lớn thì chúng ta nên tìm một giải thuật khác tối ưu hơn và nhanh hơn nhé.
Thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++
Qua phần trên chắc các bạn cũng đã hiểu sơ qua về thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++ rồi đúng không ạ. Vậy hãy xem thuật toán tìm kiếm tuyến tính dưới đây nhé, mình sẽ giải thích ngay bên dưới.
int linearSearch(int arr[], int n, int x){ //Lặp từng phần tử của mảng và kiểm tra. for(int i = 0; i < n; i++) if (arr[i] == x) return i; // Trả về -1 nếu đã duyệt hết mà ko tìm thấy. return -1; }
Trong đó:
- arr[] là mảng bao gồm các phần tử.
- n là số lượng phần tử trong mảng.
- x là giá trị cần tìm.
Giải thích thuật toán:
- Sử dụng vòng lặp for lặp từ 0 đến n - 1 (vì mảng bắt đầu từ 0 nên chúng ta phải lặp từ 0).
- Trong vòng lặp xét điều kiện nếu tồn tại giá trị a[i] = x thì trả về vị trí i của phần tử đó.
Bây giờ để hiểu rõ hơn, mình sẽ thực hiện một ví dụ tìm kiếm giá trị x có tồn tại trong mảng hay không nhé. Nếu có thì hiển thị vị trí của nó trong mảng. Chương trình sẽ được viết bằng hai ngôn ngữ C và C++, các bạn có thể tham khảo nhé.
Chương trình C:
#include <stdio.h> int linearSearch(int arr[], int n, int x){ //Lặp từng phần tử của mảng và kiểm tra. for(int i = 0; i < n; i++) if (arr[i] == x) return i; // Trả về -1 nếu đã duyệt hết mà ko tìm thấy. return -1; } int main(void) { int n,x, result; do{ printf("Nhập vào số lượng phần tử của mảng: "); scanf("%d", &n); if(n <= 0) printf("Vui lòng nhập số lượng phần tử lớn hơn 0!!!\n"); }while(n <= 0); int a[n]; //nhập các phần tử mảng for(int i=0; i<n; i++){ printf("Nhập vào phần tử a[%d]: ",i); scanf("%d",&a[i]); } printf("Nhập giá trị x cần tìm: "); scanf("%d", &x); result = linearSearch(a, n, x); if(result == -1) printf("Không tìm thấy giá trị %d trong mảng.\n",x); else printf("Đã tìm thấy giá trị %d tại vị trí %d",x,result); printf("\n----------------------------\n"); printf("Chương trình này được đăng tại codehow.net"); return 0; }
Kết quả:
Chương trình C++:
#include <iostream> using namespace std; int linearSearch(int arr[], int n, int x){ //Lặp từng phần tử của mảng và kiểm tra. for(int i = 0; i < n; i++) if (arr[i] == x) return i; // Trả về -1 nếu đã duyệt hết mà ko tìm thấy. return -1; } int main() { int n,x, result; do{ cout << "Nhập vào số lượng phần tử của mảng: "; cin >> n; if(n <= 0) cout<<"Vui lòng nhập số lượng phần tử lớn hơn 0!!!\n"; }while(n <= 0); int a[n]; //nhập các phần tử mảng for(int i=0; i<n; i++){ cout << "Nhập vào phần tử a[" << i << "]: "; cin >> a[i]; } cout<<"Nhập giá trị x cần tìm: "; cin>>x; result = linearSearch(a, n, x); if(result == -1) cout<<"Không tìm thấy giá trị "<<x<<" trong mảng.\n"; else cout<<"Đã tìm thấy giá trị "<<x<<" tại vị trí "<<result; cout<<"\n----------------------------\n"; cout<<"Chương trình này được đăng tại codehow.net"; }
Kết quả:
Như vậy là chúng ta đã cùng nhau tìm hiểu về thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++. Ở bài tiếp theo mình sẽ giới thiệu các bạn một thuật toán tìm kiếm khác, đó là thuật toán gì thì hãy ghé thăm codehow.net nhé. Cảm ơn các bạn rất nhiều.