Tìm kiếm tuyến tính trong Python
Xét từng phần tử từ trái sang phải cho đến khi gặp giá trị cần tìm. Đơn giản và dùng được cả với list chưa sắp xếp.
- Lặp với enumerate để lấy chỉ số
- Trả về chỉ số hoặc -1
- Khi nào nên dùng tìm kiếm tuyến tính
Tìm kiếm tuyến tính là gì?
Vấn đề
Có lúc dữ liệu không được sắp xếp, hoặc bạn chỉ tìm một lần: một danh sách tên ngắn, các đơn hàng hôm nay, lỗi đầu tiên trong file log. Bạn cần cách tìm đơn giản nhất mà lúc nào cũng dùng được.
Hình dung đời thường
Tìm kiếm tuần tự (linear search) giống tìm chùm chìa khóa trong một dãy túi áo. Bạn xem túi đầu tiên, rồi túi tiếp theo, từng cái một, và dừng ngay khi thấy. Nếu tới túi cuối cùng mà vẫn chưa thấy thì chìa khóa không có ở đó.
for index, value in enumerate(values):🧥 Xem lần lượt từng túiif value == target:🔑 Chìa khóa có ở đây không?return index✅ Tìm thấy: dừng tìmreturn -1❌ Đã xem hết các túi: không thấyTìm kiếm tuần tự xem lần lượt các phần tử của tập hợp cho tới khi gặp giá trị cần tìm, mất tối đa O(n) bước nhưng không cần sắp xếp.
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.
Khi nào nên sử dụng?
- Tập hợp nhỏ hoặc chưa sắp xếp.
- Chỉ tìm một lần, khi sắp xếp trước còn tốn hơn.
- Tìm phần tử đầu tiên thỏa một điều kiện, chứ không chỉ tìm đúng một giá trị.
Khi nào chưa cần
- Tìm nhiều lần trên cùng một tập dữ liệu lớn: sắp xếp một lần rồi tìm nhị phân, hoặc dựng set hay dictionary.
- Chỉ cần biết giá trị có mặt hay không:
target in valueslàm đúng việc đó với ít code hơn.
Mô phỏng Tìm kiếm tuyến tính (linear search) 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ụ
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ả khi chạy
3
Giải thích code
Hàm enumerate() cung cấp cả vị trí và giá trị của từng phần tử. Ngay khi gặp giá trị cần tìm, hàm trả về vị trí đó, ở đây là 3. Nếu duyệt hết danh sách mà không thấy, hàm trả về -1. Trong trường hợp xấu nhất, thuật toán phải kiểm tra mọi phần tử nên độ phức tạp là O(n).
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 thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Lỗi hay gặp
Trả về -1 ngay trong vòng lặp
Hàm bỏ cuộc ngay khi gặp phần tử đầu tiên không khớp.
for index, value in enumerate(values):
if value == target:
return index
return -1
for index, value in enumerate(values):
if value == target:
return index
return -1
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
- First Negative Index Find where the first negative number appears. Dễ
- Giá trị nhỏ nhất trong mảng Tìm giá trị nhỏ nhất trong một danh sách. Dễ