Tìm hiểu về giải thuật tìm kiếm tuyến tính Linear Search với minh họa bằng c++

Trong bài viết này Stanford sẽ cùng các bạn học lập trình tìm hiểu về giải thuật tìm kiếm tuyến tính Linear Search cũng như minh họa giải thuật này bằng lập trình C++.

Tìm kiếm tuyến tính (Linear Search)

Tìm kiếm tuyến tính (Linear Search) là một thuật toán tìm kiếm đơn giản, trong đó mỗi phần tử của danh sách được kiểm tra tuần tự cho đến khi tìm thấy phần tử cần tìm hoặc danh sách kết thúc.

Đặc điểm của Tìm kiếm tuyến tính:
  • Đơn giản và dễ triển khai: Thuật toán này rất dễ hiểu và dễ lập trình.
  • Không yêu cầu danh sách phải được sắp xếp: Tìm kiếm tuyến tính có thể được áp dụng cho cả danh sách đã sắp xếp và chưa sắp xếp.
  • Hiệu suất: Trong trường hợp xấu nhất, thuật toán phải kiểm tra tất cả các phần tử trong danh sách, do đó có độ phức tạp thời gian là O(n) với n là số phần tử trong danh sách.


Minh họa bằng lập trình C++:

Sau khi đã hiểu về ý tưởng của giải thuật tìm kiếm tuyến tính. Tiếp theo chúng ta sẽ lập trình một ví dụ về cách triển khai thuật toán tìm kiếm tuyến tính trong lập trình C++ như sau:

#include <iostream>
using namespace std;
 
int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i; // Trả về chỉ số của phần tử tìm thấy
        }
    }
    return -1; // Trả về -1 nếu không tìm thấy phần tử
}
 
int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 30;
 
    int result = linearSearch(arr, n, key);
    if (result != -1) {
        cout << "Phần tử " << key << " được tìm thấy tại chỉ số " << result << endl;
    } else {
        cout << "Phần tử " << key << " không được tìm thấy trong mảng" << endl;
    }
 
    return 0;
}
Trong ví dụ này, hàm linearSearch sẽ duyệt qua từng phần tử của mảng arr để tìm phần tử có giá trị bằng key. Nếu tìm thấy, hàm sẽ trả về chỉ số của phần tử đó; nếu không, hàm sẽ trả về -1.

Ưu và nhược điểm của Tìm kiếm tuyến tính:

Ưu điểm:

  • Dễ hiểu và dễ triển khai.
  • Không yêu cầu danh sách phải được sắp xếp.

Nhược điểm:

  • Hiệu suất không cao đối với danh sách lớn, do phải kiểm tra từng phần tử.
  • Không hiệu quả bằng các thuật toán tìm kiếm khác như tìm kiếm nhị phân (binary search) khi áp dụng cho danh sách đã sắp xếp.

Như vậy trong bài viết này Stanford đã chia sẻ cho các bạn hiểu hơn về giải thuật tìm kiếm tuyến tính (Linear Search). Để hiểu rõ hơn về thuật toán này bạn có thể thực hiện lập trình cài đặt thuật toán tìm kiếm tuyến tính như hướng dẫn trong bài viết. Bạn có thể tìm hiểu thêm về danh sách liên kết vòng ở đây: danh sách liên kết vòng. Chúc các bạn thành công !

Bên cạnh đó bạn có thể bắt đầu ngay con đường chinh phục trở thành lập trình viên chuyên nghiệp trong tương lai của mình bằng việc đăng ký tham gia khoá học lập trình tại đây: http://bit.ly/2SLPYFF. Hoặc gọi ngay cho Stanford theo hotline: 0963.723.236 - 0866.586.366 để được gọi lại tư vấn trực tiếp nhé.

==========🎬 🎬 🎬==========
☎️STANFORD – ĐÀO TẠO VÀ PHÁT TRIỂN CÔNG NGHỆ
Hotline: 0963 723 236 - 0866 586 366
Website: https://stanford.com.vn
Facebook: https://www.facebook.com/Stanford.com.vn
Youtube: http://bit.ly/2TkKT7I

Tags: giải thuật tìm kiếm tuyến tính, Linear Search