Bỏ qua đến nội dung chính
Mục lục

Tìm kiếm tuyến tính (linear search) trong Python

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 11/20 · Chương 23

Cấu trúc dữ liệu và giải thuật

  • 7 phút
  • Cơ bản
  • Python 3.14
  • Cập nhật

Tìm kiếm tuyến tính (linear search) là cách tìm đơn giản: xét lần lượt từng phần tử từ đầu list, dừng ngay khi gặp thứ cần tìm. Bạn dùng nó khi cần biết khách mang mã K07 đứng ở vị trí nào trong hàng chờ ở quầy, hay ai là người đầu tiên đã chờ quá 30 phút.

Cần biết trước: duyệt list, enumerate() và Big O.

Dò từng phần tử bằng vòng lặp for

Hàm tìm kiếm tuyến tính nhận một list và giá trị cần tìm. Nó duyệt list bằng enumerate() để có cả vị trí lẫn phần tử, và trả về vị trí ngay khi phần tử khớp. Nếu vòng lặp chạy hết mà không gặp, hàm trả về -1, một số không bao giờ là vị trí thật trong list.

python
hang_cho = ["K03", "K11", "K07", "K20", "K07"]

def tim(ds, x):
    for i, gia_tri in enumerate(ds):
        if gia_tri == x:
            return i
    return -1

print(tim(hang_cho, "K07"))
print(tim(hang_cho, "K99"))

KẾT QUẢ

2
-1

Mã K07 có hai khách mang, nhưng hàm trả về 2, vị trí của người đứng trước. return thoát khỏi hàm ngay lập tức, nên vòng lặp không bao giờ tới người thứ hai. Dòng return -1 nằm sau vòng lặp, ngang hàng với for, nên chỉ chạy khi đã xét hết hàng. Đổi "K99" thành "K20" rồi chạy lại: dòng cuối in 3.

Trả về -1 cho trường hợp không có là quy ước của bài. Một số hàm khác chọn None, và người gọi luôn phải kiểm kết quả trước khi dùng nó làm chỉ số.

Đếm số bước của tìm kiếm tuyến tính

Mỗi lượt của vòng lặp là một phép so sánh. Hàm dưới đây đếm thêm số lượt đó và trả về cả hai.

python
def tim_dem(ds, x):
    buoc = 0
    for i, gia_tri in enumerate(ds):
        buoc += 1
        if gia_tri == x:
            return i, buoc
    return -1, buoc

ds = list(range(1000))
print(tim_dem(ds, 0))
print(tim_dem(ds, 999))
print(tim_dem(ds, -5))

KẾT QUẢ

(0, 1)
(999, 1000)
(-1, 1000)

Thứ cần tìm ở đầu list thì chỉ mất 1 bước, đó là trường hợp tốt nhất. Nằm ở cuối list hay không có trong list thì mất đủ 1000 bước, đó là trường hợp xấu nhất. Tính trung bình, phần tử có mặt nằm đâu đó giữa list, nên hàm xét khoảng nửa list.

Big O lấy trường hợp xấu nhất: tìm kiếm tuyến tính tốn O(n) với n phần tử. Hàng dài gấp 10 thì số bước xấu nhất cũng gấp 10. Toán tử in trên list và phương thức list.index() cũng dò từng phần tử như thế bên trong, nên cũng tốn O(n) (xem duyệt list và các phương thức của list).

Dừng sớm bằng break

Một cách viết khác dùng biến vi_tri để nhớ kết quả, rồi trả về sau vòng lặp. Cách này cần chú ý: gặp phần tử khớp rồi thì phải dừng vòng lặp lại.

python
def tim(ds, x):
    vi_tri = -1
    for i, gia_tri in enumerate(ds):
        if gia_tri == x:
            vi_tri = i
            break
    return vi_tri

print(tim(["K03", "K07", "K11", "K07"], "K07"))

KẾT QUẢ

1

break thoát khỏi vòng lặp ở lần khớp đầu tiên, rồi hàm trả về vị trí đã nhớ. Cách này hợp khi sau vòng lặp bạn còn việc khác phải làm trước khi trả về. Nếu không, return i ngay trong vòng lặp ngắn hơn.

Tìm mọi vị trí và khi nào tìm tuyến tính là đủ

Muốn biết mọi vị trí khớp thay vì chỉ vị trí đầu, bạn không dừng sớm mà gom từng vị trí vào một list:

python
hang_cho = ["K03", "K11", "K07", "K20", "K07"]
vi_tri = []
for i, ma in enumerate(hang_cho):
    if ma == "K07":
        vi_tri.append(i)
print(vi_tri)
print(len(vi_tri), "lần")

KẾT QUẢ

[2, 4]
2 lần

Cách này luôn xét hết list, vì phải chắc không bỏ sót ai. Đổi ma == "K07" thành ma == "K20" rồi chạy lại: dòng đầu in [3].

Tìm kiếm tuyến tính là đủ trong nhiều việc hằng ngày. List vài trăm, vài nghìn phần tử thì máy dò hết trong nháy mắt. List chưa sắp xếp, và bạn chỉ tìm một vài lần, thì cũng không có cách nào nhanh hơn, vì phần tử cần tìm có thể nằm bất cứ đâu. Điều kiện tìm không phải phép bằng, như "chờ quá 30 phút", thì cũng phải dò từng người.

Khi phải tìm rất nhiều lần trên cùng một list lớn, hãy đổi cách lưu. Tra một set hay một dict chỉ tốn khoảng một bước, như bài Big O đã đo. List đã sắp xếp thì dùng tìm kiếm nhị phân, mỗi bước bỏ đi một nửa list.

Kiểm tra nhanh

  1. Với hang_cho = ["K03", "K11", "K07", "K20", "K07"] và hàm tim_dem() của bài, tim_dem(hang_cho, "K07") trả về gì?

    • (2, 2)
    • (2, 3)
    • (4, 5)
  2. Với hàm tim() đặt return -1 trong nhánh else của vòng lặp, tim(["K07", "K11"], "K11") trả về gì?

    • -1
    • 1
    • 0
  3. Những thân hàm nào làm tim(["K03", "K07", "K07"], "K07") trả về 1?

    • Duyệt bằng enumerate(), gặp phần tử khớp thì return i, sau vòng lặp return -1
    • Gán vi_tri = i mỗi lần khớp, không có break, sau vòng lặp return vi_tri
    • Gán vi_tri = i rồi break, sau vòng lặp return vi_tri
    • Gặp phần tử khớp thì return i, nhánh else thì return -1
  4. List có một triệu phần tử và không chứa giá trị cần tìm. Tìm kiếm tuyến tính so sánh bao nhiêu lần?

    • Khoảng 20 lần
    • Khoảng nửa triệu lần
    • Đúng một triệu lần
Đúng hết lần đầu +15 XP

Bài tập

Khách đầu tiên chờ quá lâu

Viết hàm khach_cho_lau(phut_cho, gioi_han). phut_cho là list số phút mỗi khách đã chờ, theo thứ tự đứng trong hàng. Hàm trả về vị trí (tính từ 0) của khách đầu tiên đã chờ lâu hơn hẳn gioi_han phút. Không có khách nào như vậy, kể cả khi hàng rỗng, thì trả về -1.

Hàm phải dừng ngay khi gặp khách đó: trình chấm có một hàng 1000 khách và đếm số phần tử hàm đọc. Đừng sửa phut_cho.

Ví dụ: khach_cho_lau([12, 25, 41, 8, 50], 30) trả về 2.

Trả về: vị trí của khách, một int.

python
def khach_cho_lau(phut_cho, gioi_han):
    pass  # Viết thân hàm thay cho dòng này

Tóm tắt

  • Tìm kiếm tuyến tính xét lần lượt từng phần tử từ đầu list và dừng ở phần tử khớp đầu tiên.

  • enumerate() cho cả vị trí lẫn phần tử, và return i trong vòng lặp vừa trả kết quả vừa dừng.

  • return -1 cho trường hợp không có nằm sau vòng lặp, không nằm trong nhánh else.

  • Dùng biến nhớ vị trí thì cần break để không lấy nhầm vị trí cuối cùng.

  • Trường hợp xấu nhất tốn n bước, tức O(n), và vẫn là đủ cho list nhỏ, list chưa sắp xếp hay điều kiện tìm bất kỳ.

Câu hỏi thường gặp

Thuật toán tìm kiếm tuyến tính chậm hơn cách tìm chia đôi bao nhiêu?

Tìm kiếm tuyến tính chạy trên list bất kỳ và tốn O(n). Tìm kiếm nhị phân chỉ chạy trên list đã sắp xếp, nhưng mỗi bước bỏ đi một nửa nên chỉ tốn O(log n). List một triệu phần tử cần tối đa một triệu bước với cách thứ nhất, khoảng 20 bước với cách thứ hai.

Có nên tự viết hàm tìm khi đã có toán tử in?

Khi chỉ cần biết có hay không, hay tìm một giá trị bằng nhau, toán tử in và list.index() gọn hơn và chạy nhanh hơn vòng lặp tự viết. Tự viết khi điều kiện tìm phức tạp hơn phép bằng, như khách chờ quá 30 phút, hay khi bạn cần đếm số bước.

Tìm từ cuối list lên thì viết thế nào?

Duyệt chỉ số từ len(ds) - 1 về 0 bằng range(len(ds) - 1, -1, -1) và trả về chỉ số đầu tiên khớp. Cách này cho vị trí khớp cuối cùng mà vẫn dừng sớm, hợp khi bạn cần thao tác gần nhất trong lịch sử thao tác.

Chủ đề

linear search

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập