Thuật toán 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 đơn giản nhất trong các thuật toán tìm kiếm dữ liệu.

Cách thức hoạt động của thuật toán này như sau:

1. Để tìm phần tử x trong danh sách đã cho, ta duyệt từ đầu đến cuối danh sách.
2. Nếu phần tử được tìm thấy, trả về vị trí của nó trong danh sách.
3. Nếu phần tử không được tìm thấy, trả về giá trị -1.

Độ phức tạp của thuật toán tìm kiếm tuyến tính (Linear search) là O(n), với n là số lượng phần tử trong danh sách.

Dưới đây là đoạn code Python mẫu để tìm kiếm một phần tử trong danh sách sử dụng thuật toán tìm kiếm tuyến tính:

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

Ví dụ: Cho danh sách [64, 25, 12, 22, 11] và tìm kiếm phần tử có giá trị là 22. Sử dụng thuật toán tìm kiếm tuyến tính, ta có kết quả là 3.

arr = [64, 25, 12, 22, 11]
x = 22
result = linear_search(arr, x)
print(result) # Kết quả là 3