Thuật toán tìm kiếm tuyến tính trong Python
Linear search hoạt động cả khi dữ liệu chưa sắp xếp.
Tìm kiếm tuyến tính là gì?
Tìm kiếm tuyến tính duyệt lần lượt từng phần tử từ đầu danh sách cho đến khi tìm thấy giá trị hoặc đã kiểm tra hết danh sách. Dữ liệu không cần được sắp xếp trước.
Cách thuật toán hoạt động
- Bắt đầu tại phần tử có chỉ số 0.
- So sánh phần tử hiện tại với giá trị cần tìm.
- Nếu bằng nhau, trả về chỉ số; nếu không, chuyển sang phần tử tiếp theo.
- Nếu duyệt hết danh sách, trả về -1.
Độ phức tạp: O(n) thời gian trong trường hợp trung bình và xấu nhất; O(1) bộ nhớ bổ sung.
Mô phỏng Thuật toán tìm kiếm tuyến tính trong Python
O(n)Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.
Code ví dụ
main.py
def linear_search(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(linear_search([14, 3, 27, 8, 19], 8))Kết quả dự kiến
3Cách hoạt động
Mỗi phần tử được so sánh tối đa một lần: thời gian O(n), bộ nhớ O(1).
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy sửa code theo các bài tập dưới đây để hiểu rõ cách hoạt động thay vì chỉ sao chép kết quả.
- Kiểm tra trường hợp rỗng, một phần tử và giá trị trùng lặp.
- In trạng thái sau từng bước để quan sát thuật toán.
- Đo thời gian với 100, 1.000 và 10.000 phần tử rồi so sánh cách giải khác.