🔍 Thuật toán tìm kiếm

Tìm kiếm là bài toán nền tảng nhất trong lập trình: cho một tập dữ liệu, tìm phần tử thỏa điều kiện nào đó. Cách “chắc ăn” nhất luôn là duyệt tuần tự - nhưng nếu dữ liệu có sẵn một tính chất đặc biệt (đã sắp xếp, đã băm sẵn…), ta có thể khai thác tính chất đó để tìm nhanh hơn rất nhiều, đánh đổi lại bằng việc phải chuẩn bị dữ liệu trước.

Linear Search - khi không có gì để khai thác

Duyệt qua từng phần tử cho đến khi tìm thấy hoặc hết mảng. Không đòi hỏi gì ở dữ liệu, nhưng độ phức tạp luôn là O(n).

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

Binary Search - khai thác tính có thứ tự

Nếu mảng đã sắp xếp, ta không cần xét từng phần tử: so sánh với phần tử ở giữa, rồi loại bỏ hẳn một nửa mảng không còn khả năng chứa target. Lặp lại cho đến khi tìm thấy hoặc khoảng tìm kiếm rỗng.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Độ phức tạp O(log n) - với một triệu phần tử, chỉ cần tối đa khoảng 20 lần so sánh. Đổi lại, binary search có hai ràng buộc quan trọng:

• Chỉ áp dụng được khi mảng đã sắp xếp. Nếu dữ liệu chưa sắp xếp, phải sắp xếp trước (tốn O(n log n)) - chỉ đáng làm nếu bạn sẽ tìm kiếm nhiều lần trên cùng dữ liệu đó.
• Chỉ hiệu quả trên cấu trúc truy cập ngẫu nhiên (array) - không dùng được trên linked list, vì việc “nhảy thẳng đến phần tử giữa” đòi hỏi truy cập O(1) theo chỉ số.

Mẹo

Với dữ liệu nhỏ, linear search đôi khi lại nhanh hơn binary search trên thực tế, vì mỗi vòng lặp binary search tốn nhiều phép toán hơn (tính mid, so sánh, cập nhật 2 biên) so với một phép so sánh đơn giản của linear search. Chỉ khi n đủ lớn, ưu thế O(log n) mới thắng rõ rệt.

Biến thể: tìm điểm chèn và tìm biên

Binary search không chỉ tìm một phần tử cụ thể - nó còn trả lời được câu hỏi tổng quát hơn: “chèn giá trị này vào đâu để mảng vẫn có thứ tự?”

def search_insert_position(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left  # vị trí left chính là điểm chèn hợp lệ

Khi mảng có phần tử trùng lặp, hàm trên tự nhiên trả về vị trí chèn bên trái - tức chỉ số của lần xuất hiện đầu tiên (biên trái) của target, nếu nó đã có trong mảng. Muốn tìm biên phải (lần xuất hiện cuối cùng), cách gọn nhất là tái sử dụng chính hàm tìm điểm chèn: tìm điểm chèn của target + 1, rồi lùi lại một bước.

def right_bound(arr, target):
    i = search_insert_position(arr, target + 1)
    return i - 1  # phần tử ngay trước điểm chèn của target + 1

Mẫu số chung của các biến thể này: thay vì viết một hàm nhị phân riêng cho từng câu hỏi, hãy quy chúng về cùng một hàm gốc “tìm điểm chèn” - vừa ít code, vừa ít khả năng viết sai điều kiện biên (lỗi off-by-one là lỗi phổ biến nhất khi tự viết binary search).

Tìm kiếm trong mảng đã xoay

Một mảng đã sắp xếp rồi bị “xoay” tại một điểm bất kỳ (ví dụ [4,5,6,7,0,1,2]) không còn hoàn toàn có thứ tự, nhưng vẫn giữ được một tính chất quan trọng: tại bất kỳ điểm giữa nào, ít nhất một nửa mảng vẫn có thứ tự. Binary search vẫn áp dụng được, chỉ cần thêm một bước kiểm tra xem nửa nào đang có thứ tự trước khi quyết định thu hẹp bên nào.

def search_rotated(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[left] <= arr[mid]:          # nửa trái có thứ tự
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:                               # nửa phải có thứ tự
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Khi cần tra cứu nhiều lần: đổi sang hash table

Nếu bài toán không chỉ tìm một lần mà cần tra cứu lặp đi lặp lại trên cùng một tập dữ liệu, hãy cân nhắc trả giá O(n) bộ nhớ để đổi lấy tra cứu O(1): xây một hash table một lần, rồi mọi lần tìm kiếm sau đó gần như tức thời - nhanh hơn cả binary search. Đánh đổi: hash table không giữ được thứ tự dữ liệu, nên không dùng được cho các câu hỏi kiểu “phần tử nhỏ nhất lớn hơn X” hay duyệt theo khoảng.

Chọn thuật toán nào?

Cách tìm	Độ phức tạp	Yêu cầu	Phù hợp khi
Linear search	O(n)	Không	Dữ liệu nhỏ, hoặc chỉ tìm 1 lần
Binary search	O(log n)	Mảng đã sắp xếp	Dữ liệu lớn, ổn định, ít thay đổi
Hash table	O(1) trung bình	Tốn thêm O(n) bộ nhớ	Tra cứu rất nhiều lần, không cần thứ tự
Cây tìm kiếm (BST cân bằng)	O(log n)	Cấu trúc cây	Dữ liệu thay đổi liên tục, vẫn cần giữ thứ tự

Ghi chú

Không có thuật toán “tốt nhất tuyệt đối” - bảng trên chính là ví dụ điển hình của đánh đổi giữa thời gian tra cứu, bộ nhớ, và mức độ ràng buộc lên dữ liệu đầu vào (đã đề cập ở trang Độ phức tạp bộ nhớ).