Thuật toán Python

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.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • 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 8 trong [14, 3, 27, 8, 19]
14[0] ✗
3[1] ✗
27[2] ✗
8[3] ✓
19[4]
↑ trả về 3

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ó ở đó.

Từ việc lục túi áo đến code
for index, value in enumerate(values):🧥 Xem lần lượt từng túi
if value == target:🔑 Chìa khóa có ở đây không?
return index✅ Tìm thấy: dừng tìm
return -1❌ Đã xem hết các túi: không thấy
Xem từng phần tử một; dừng ở lần khớp đầu tiên.
Định nghĩa ngắn gọn

Tì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

  1. Bắt đầu tại phần tử có chỉ số 0.
  2. So sánh phần tử hiện tại với giá trị cần tìm.
  3. Nếu bằng nhau, trả về chỉ số; nếu không, chuyển sang phần tử tiếp theo.
  4. 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.

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 values là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ụ

Chạy code →
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))
Lấy nút Run cho ví dụ này

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.

  1. 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.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đ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.
Chạy trong trình biên dịch Python →

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.

Sai
for index, value in enumerate(values):
    if value == target:
        return index
    return -1
Cách sửa
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.

Tất cả thử thách