Trong bài viết này hãy cùng TUICOCACH.COM giải bài tập Tìm kiếm phần tử trong mảng lập trình C/C++. Đây là một dạng bài tập rất cơ bản giúp cho việc luyện tập code lập trình C/C++.
Tìm kiếm phần tử trong mảng
Tìm kiếm phần tử trong mảng là một toán được áp dụng khá nhiều trong thực tế, vậy làm sao để tìm kiếm, và cách tối ưu nhất để tìm kiếm?. Mình sẽ giới thiệu tới các bạn hai thuật toán được áp dụng nhiều nhất.
Tìm kiếm tuần tự
Tìm kiếm tuần tự(tuyến tính) là cách tìm kiếm đơn giản nhất mà với những bạn khi mới bắt đầu học cũng rất dễ áp dụng. Độ phức tạp thuật toán trường hợp xấu nhất là O(n).
Ý tưởng giải quyết bài toán theo tìm kiếm tuần tự là chúng ta sẽ duyệt lần lượt từng phần tử trong mảng cho đến khi nào ta gặp phần tử cần tìm kiếm thì dừng vòng lặp, hoặc cho đến khi kết thúc vòng lặp mà không tìm thấy.
Ta viết chương trình tìm kiếm tuần tự như sau, chương trình này nếu tìm thấy phần tử thì sẽ trả về chỉ số mảng của phần tử đó, ngược lại trả về -1.
#include <stdio.h>
//Hàm nhập mảng
void nhapMang(int n, int A[]){
for(int i = 0; i<n;i++)
{
printf("A[%d] = ", i);
scanf("%d", &A[i]);
}
}
//Hàm xuất mảng
void xuatMang(int n, int A[]){
for(int i = 0; i<n;i++)
{
printf("%d ", A[i]);
}
}
//Hàm tìm kiếm tuần tự
int timKiemTuanTu(int n, int A[], int key){
for(int i = 0; i<n; i++)
{
if(A[i] == key) return i;
}
return -1;
}
int main()
{
int n;
int A[100];
printf("Nhap n: ");
scanf("%d", &n);
printf("Nhap mang: ");
nhapMang(n,A);
xuatMang(n,A);
int key;
printf("\n\nNhap phan tu can tim kiem: ");
scanf("%d", &key);
int vt = timKiemTuanTu(n, A, key);
if(vt != -1){
printf("Tim thay phan tu => vi tri %d", vt+1);
}
else printf("Khong tim thay phan tu");
}
Tìm kiếm nhị phân(Chặt nhị phân)
Ý tưởng của thuật toán tìm kiếm nhị phân đó là mỗi bước thực hiện chúng ta sẽ chia mảng ra làm 2 phần, và cứ thế chia nhỏ chia nhỏ dần, vì vậy thuật toán này độ phức tạp chỉ là O(log(n)). Tuy nhiên thuật toán này lại có một nhược điểm đó là chỉ có thể thực hiện trên mảng đã được sắp xếp.
Để hiểu rõ hơn và áp dụng được thuật toán tìm kiếm nhị phân bạn đọc chi tiết trong bài viết này.
[Xem tất cả bài viết chủ đề C/C++ tại đây]
