Login

Tìm kiếm tuần tự và tìm kiếm nhị phân: khác nhau thế nào?

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Tìm một thứ trong một tập hợp là bài toán xuất hiện ở khắp mọi nơi. Hai cách tiếp cận cơ bản nhất là tìm từng phần tử một, hoặc tận dụng thứ tự để loại bỏ một nửa mỗi bước. Khác biệt về tốc độ giữa chúng thật đáng kinh ngạc.

Tìm kiếm tuần tự (linear search)

Ý tưởng: xem từng phần tử từ đầu đến cuối cho đến khi gặp thứ cần tìm.

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

print(tim_tuan_tu([7, 3, 9, 1], 9))   # 2
print(tim_tuan_tu([7, 3, 9, 1], 5))   # -1

Ưu điểm là đơn giản và chạy được trên danh sách bất kỳ, không cần sắp xếp. Nhược điểm: trường hợp xấu nhất phải xem cả n phần tử, tức độ phức tạp O(n).

Tìm kiếm nhị phân (binary search)

Nếu danh sách đã sắp xếp, bạn có thể làm tốt hơn nhiều. Hãy so sánh với phần tử ở giữa:

  • Bằng giá trị cần tìm: xong.
  • Giá trị cần tìm nhỏ hơn: chỉ tìm tiếp nửa bên trái.
  • Giá trị cần tìm lớn hơn: chỉ tìm tiếp nửa bên phải.

Mỗi bước loại bỏ một nửa, giống trò chơi đoán số từ 1 đến 100: hỏi "lớn hơn 50 không?" rồi tiếp tục chia đôi.

def tim_nhi_phan(ds, can_tim):
    trai, phai = 0, len(ds) - 1
    while trai <= phai:
        giua = (trai + phai) // 2
        if ds[giua] == can_tim:
            return giua
        if ds[giua] < can_tim:
            trai = giua + 1
        else:
            phai = giua - 1
    return -1

ds = [1, 3, 5, 7, 9, 11, 13]
print(tim_nhi_phan(ds, 9))    # 4
print(tim_nhi_phan(ds, 4))    # -1

Nhanh hơn bao nhiêu?

Tìm nhị phân có độ phức tạp O(log n). Với khoảng một triệu phần tử, tìm tuần tự có thể cần đến một triệu bước, trong khi tìm nhị phân chỉ cần chừng 20 bước, vì 2 mũ 20 xấp xỉ một triệu. Khi dữ liệu tăng gấp đôi, tìm nhị phân chỉ thêm đúng một bước.

Tiêu chíTuần tựNhị phân
Yêu cầu dữ liệuKhôngPhải sắp xếp
Độ phức tạpO(n)O(log n)
Độ khó viếtRất dễDễ sai chi tiết

Những chỗ dễ sai

  1. Điều kiện dừng: dùng trai <= phai chứ không phải <, nếu không sẽ bỏ sót trường hợp còn đúng một phần tử.
  2. Cập nhật biên: phải là giua + 1 và giua - 1, nếu chỉ gán giua có thể lặp vô hạn.
  3. Quên sắp xếp trước khi tìm nhị phân sẽ cho kết quả sai mà không báo lỗi.
  4. Tràn số ở một số ngôn ngữ khi tính (trai + phai) / 2 với mảng rất lớn; cách an toàn là trai + (phai - trai) / 2.

Khi nào chọn cái nào?

Nếu chỉ tìm một lần trên dữ liệu chưa sắp xếp, tìm tuần tự thường hợp lý vì sắp xếp tốn nhiều công hơn. Nếu bạn tìm nhiều lần trên cùng một tập dữ liệu, sắp xếp một lần rồi tìm nhị phân sẽ có lợi. Còn nếu cần tra cứu theo khóa liên tục, bảng băm thường nhanh hơn nữa. Thư viện chuẩn của Python có sẵn module bisect cho tìm nhị phân, nên ngoài bài tập, bạn không cần tự viết lại.

Biến thể hay gặp: tìm vị trí chèn

Trong thực tế, ta thường không chỉ muốn biết "có hay không" mà còn cần biết vị trí để chèn một giá trị vào danh sách đã sắp xếp. Chỉ cần đổi giá trị trả về:

def vi_tri_chen(ds, gia_tri):
    trai, phai = 0, len(ds)
    while trai < phai:
        giua = (trai + phai) // 2
        if ds[giua] < gia_tri:
            trai = giua + 1
        else:
            phai = giua
    return trai

print(vi_tri_chen([1, 3, 5, 7], 4))   # 2
print(vi_tri_chen([1, 3, 5, 7], 9))   # 4

Ở biến thể này khoảng tìm là nửa mở [trai, phai), nên điều kiện dừng là trai < phai. Đây cũng là cách module bisect của Python hoạt động. Một ứng dụng thú vị khác của ý tưởng nhị phân là "tìm nhị phân trên đáp án": nếu bạn có thể kiểm tra một giá trị có thỏa điều kiện hay không và tính chất đơn điệu (nếu x thỏa thì mọi giá trị lớn hơn cũng thỏa), bạn có thể nhị phân để tìm giá trị nhỏ nhất thỏa. Hãy thử với bài tìm căn bậc hai nguyên của một số.

Kết luận

Tìm kiếm nhị phân là ví dụ đẹp nhất của tư duy "chia để trị": dùng thứ tự có sẵn để loại bỏ một nửa không gian tìm kiếm mỗi bước. Hãy tự cài đặt nó mà không nhìn tài liệu, rồi kiểm thử với mảng rỗng, một phần tử, và giá trị không tồn tại.

Muốn học bài bản và có người hướng dẫn? Hãy xem các khóa học trên codebem.com để đi từ nền tảng đến dự án thực tế.

author_photo
Nguyễn Đình Cường

0 comment