Giải thuật Tìm kiếm tuyến tính (Linear Search) trong C++ - Giải thích, Ví dụ và Mã nguồn

Thuật toán tìm kiếm tuyến tính là một phương pháp đơn giản để tìm kiếm một phần tử cụ thể trong một danh sách. Thuật toán này hoạt động bằng cách kiểm tra từng phần tử trong danh sách một cách tuần tự cho đến khi tìm thấy phần tử cần tìm hoặc duyệt qua toàn bộ danh sách.

Cách hoạt động

1. Bắt đầu từ phần tử đầu tiên trong danh sách.
2. So sánh phần tử hiện tại với giá trị cần tìm kiếm.
3. Nếu phần tử hiện tại bằng giá trị cần tìm, thuật toán kết thúc và trả về vị trí của phần tử.
4. Nếu không, tiếp tục duyệt qua các phần tử còn lại trong danh sách.
5. Nếu duyệt qua toàn bộ danh sách mà không tìm thấy phần tử cần tìm, thuật toán trả về một giá trị biểu thị không tìm thấy.

Ví dụ

Giả sử chúng ta có một danh sách các số nguyên và chúng ta muốn tìm kiếm số 34 trong danh sách.

Danh sách: {12, 45, 67, 89, 34, 56, 23, 90}

1. Bắt đầu tại phần tử đầu tiên: 12. Không phải số cần tìm.
2. Tiếp tục với phần tử tiếp theo: 45. Không phải số cần tìm.
3. Tiếp tục với các phần tử còn lại: 67, 89, 34. Phần tử 34 bằng số cần tìm.
4. Thuật toán kết thúc và trả về vị trí của số 34 là 4.

Code ví dụ trong C++

#include <iostream>
#include <vector>

int linearSearch(const std::vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    std::vector<int> numbers = {12, 45, 67, 89, 34, 56, 23, 90};
    int target = 34;

    int result = linearSearch(numbers, target);

    if (result != -1) {
        std::cout << "Phan tu " << target << " duoc tim thay tai vi tri " << result << std::endl;
    } else {
        std::cout << "Phan tu " << target << " khong duoc tim thay trong mang" << std::endl;
    }

    return 0;
}

Trong ví dụ trên, chúng ta đã sử dụng hàm linearSearch để tìm kiếm số 34 trong danh sách các số nguyên. Kết quả sẽ là vị trí của số 34 trong danh sách (vị trí bắt đầu từ 0) hoặc -1 nếu không tìm thấy.