Thuật toán tìm kiếmSearch Algorithms

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Tìm kiếm là việc xác định một phần tử cụ thể, hoặc một nhóm phần tử, trong một tập dữ liệu. Roadmap nêu bốn thuật toán tìm kiếm chính: linear search, binary search, depth-first search, và breadth-first search. Hai cái đầu làm việc trên các tập dữ liệu tuyến tính và là nội dung của bài này; DFS và BFS làm việc trên tree và graph, được trình bày ở ./10-tree-data-structures.md và ./13-graph-data-structures.md.

Linear search và binary search trông như một chủ đề nhỏ đến mức tầm thường — hai thuật toán, mỗi cái mười dòng. Không phải vậy, vì hai lý do.

Lý do thứ nhất là binary search nổi tiếng là khó viết cho đúng. Jon Bentley kể rằng khi ông ra bài này cho các lập trình viên chuyên nghiệp suốt nhiều năm, khoảng 90% viết ra phiên bản có bug dù được cho bao nhiêu thời gian tùy thích. Arrays.binarySearch của Java ra đời cùng một bug tràn số nguyên tồn tại chín năm và chỉ được phát hiện năm 2006. Thuật toán chỉ có bốn dòng và mỗi dòng đều có một cái bẫy off-by-one. Cách chữa không phải là cẩn thận hơn; mà là cam kết với một template duy nhất có bất biến được viết ra rõ ràng và không bao giờ ứng biến.

Lý do thứ hai là binary search tổng quát hơn nhiều so với “tìm một phần tử trong array đã sắp xếp”. Yêu cầu thật sự của nó là một monotonic predicate — một hàm boolean trên một không gian tìm kiếm có thứ tự, nhận giá trị false, false, …, false, true, true, …, true. Mọi hàm như vậy đều có thể đảo ngược trong O(log n) lần đánh giá. Khi đã nhìn ra điều đó, “binary search trên đáp án” trở thành một trong những kỹ thuật giải bài toán có đòn bẩy lớn nhất: nó biến “tìm X nhỏ nhất sao cho Y khả thi” thành “kiểm tra xem một X cho trước có khả thi không”, mà việc sau thường dễ hơn nhiều.

Mạch thứ ba xuyên suốt bài này là sự so sánh với hash table. Hash table trả lời “có x không?” trong O(1) còn array đã sắp cần O(log n), nên hash table có vẻ thắng tuyệt đối. Không hẳn vậy, và phần nói về khi nào array đã sắp thắng chính là phần hữu dụng nhất về mặt thực tế của bài này.

Kiến thức nền tảng

Linear search

Kiểm tra từng phần tử một cho tới khi tìm thấy hoặc hết phần tử. Còn gọi là sequential search.

def linear_search(arr, target):
    """Trả về chỉ số lần xuất hiện đầu tiên của target, hoặc -1. O(n)."""
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

Độ phức tạp: best case O(1) (phần tử đầu tiên), trung bình O(n) (n/2 phép so sánh khi tìm thành công với vị trí phân bố đều) và worst case O(n), bộ nhớ O(1).

Ưu điểm của nó đều nằm ở việc không đòi hỏi điều kiện tiên quyết nào:

• Không cần dữ liệu đã sắp xếp. Nó chạy trên dữ liệu chưa sắp, đó là lựa chọn duy nhất khi dữ liệu không thể sắp xếp hoặc khi việc sắp xếp không đáng giá O(n log n).
• Không cần random access. Nó chạy trên linked list (./05-linked-lists.md), trên generator, trên một file đang được đọc từng dòng, hoặc trên một network stream. Binary search thì không: đi tới giữa một linked list tự nó đã tốn O(n), phá hỏng toàn bộ mục đích.
• Không cần tiền xử lý. Với một lần tìm kiếm duy nhất trên dữ liệu bạn sẽ không tìm lại nữa, sắp xếp trước (O(n log n)) rõ ràng tệ hơn là chỉ quét (O(n)).
• n nhỏ thì nó thắng. Dưới khoảng 20–100 phần tử, quét tuyến tính trên array liền kề thắng binary search, vì việc quét là tuần tự và dễ dự đoán nhánh, còn binary search thì nhảy lung tung và dự đoán sai ở mọi bước. Các thư viện thật đều tận dụng điều này.

Trong Python bạn sẽ viết target in arr, arr.index(target), hoặc next((i for i, x in enumerate(arr) if pred(x)), None). Cả ba đều O(n), và cả ba đều chạy vòng lặp bằng C. Performance bug kinh điển là một linear search lồng bên trong một vòng lặp khác — for x in a: if x in b là O(n·m), và chuyển b thành set trước sẽ làm nó thành O(n + m) (./07-hash-tables.md).

Binary search — ý tưởng

Trên một array đã sắp xếp, so sánh target với phần tử ở giữa. Một trong ba điều đúng: bạn tìm thấy nó, hoặc target phải nằm ở nửa trái, hoặc nó phải nằm ở nửa phải. Cách nào cũng vậy, bạn loại bỏ một nửa số ứng viên còn lại chỉ bằng một phép so sánh.

tìm 8 trong [1, 3, 5, 7, 9, 11, 13]

bước 1:  1   3   5  [7]  9  11  13     mid = 7,  7 < 8  → bỏ nửa trái và cả mid
bước 2:                  9 [11] 13     mid = 11, 11 > 8 → bỏ 11 và mọi thứ bên phải
bước 3:                 [9]            mid = 9,  9 > 8  → bỏ nó
bước 4:                 (rỗng)         → không tìm thấy; 8 thuộc về vị trí index 4

Chia đôi không gian tìm kiếm k lần còn lại n/2ᵏ ứng viên; việc tìm kiếm kết thúc khi n/2ᵏ < 1, tức là k > log₂ n. Đó là toàn bộ lập luận về độ phức tạp: O(log n), và logarit cơ số 2 rất nhỏ — một array một tỷ phần tử chỉ tốn 30 phép so sánh.

Điều kiện tiên quyết là không thể thương lượng: array phải đã được sắp xếp theo đúng phép so sánh đang dùng. Binary search trên dữ liệu chưa sắp không thỉnh thoảng trả về sai; nó trả về rác, một cách im lặng.

Template kinh điển (biên đóng)

def binary_search(arr, target):
    """Trả về một chỉ số của target trong list đã sắp arr, hoặc -1 nếu không có.
    Bất biến: nếu target có trong arr, chỉ số của nó nằm trong đoạn ĐÓNG [lo, hi]."""
    lo, hi = 0, len(arr) - 1           # hi là biên ĐÓNG (bao gồm)
    while lo <= hi:                    # [lo, hi] vẫn khác rỗng khi lo == hi
        mid = lo + (hi - lo) // 2      # tương đương (lo + hi) // 2, nhưng không tràn số
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1               # mid quá nhỏ — loại nó ra
        else:
            hi = mid - 1               # mid quá lớn — loại nó ra
    return -1                          # lo > hi: khoảng đã rỗng

Bốn quy tắc làm cho phiên bản này đúng, và mọi bug kinh điển đều là vi phạm một trong số đó:

1. hi = len(arr) - 1 vì hi là biên đóng. Viết len(arr) ở đây là đọc vượt ra ngoài array.
2. while lo <= hi, không phải <. Khi lo == hi khoảng vẫn còn đúng một ứng viên; dấu < sẽ bỏ qua nó và báo “không tìm thấy” với các khoảng một phần tử.
3. mid + 1 và mid - 1, không bao giờ là mid. arr[mid] đã được so sánh và biết chắc không phải target, nên nó phải rời khỏi khoảng — nếu không, khoảng không bao giờ co lại và vòng lặp treo.
4. lo + (hi - lo) // 2, không phải (lo + hi) // 2. Trong Python số nguyên có độ chính xác tùy ý nên cả hai đều được, nhưng trong Java, C, C++, Go, và Rust thì lo + hi tràn kiểu int 32-bit ngay khi array vượt 2³⁰ phần tử. Đây đúng là bug mà Joshua Bloch phát hiện trong JDK năm 2006 — chín năm sau khi phát hành, trong đoạn code từng được chứng minh hình thức là đúng dựa trên một mô hình giả định số nguyên không giới hạn.

Một lượt trace cụ thể

arr = [1, 3, 5, 7, 9, 11, 13], tìm 7:

Bước	lo	hi	mid	arr[mid]	So sánh	Hành động
1	0	6	3	7	7 == 7	return 3

Quá dễ — lượt trace thú vị là lượt tìm không thành công. Tìm 8:

Bước	lo	hi	mid	arr[mid]	So sánh	Hành động
1	0	6	3	7	7 < 8	lo = 4
2	4	6	5	11	11 > 8	hi = 4
3	4	4	4	9	9 > 8	hi = 3
4	4	3	—	—	lo > hi	return −1

Chú ý bước 3: đây chính là trường hợp mà while lo < hi sẽ bỏ qua, âm thầm trả về “không tìm thấy” mà chưa bao giờ xét arr[4]. Mỗi khi bạn viết một binary search, hãy trace bằng tay khoảng hai phần tử và khoảng một phần tử. Bug nằm ở đó.

Khái niệm chính

lower_bound và upper_bound — template bạn thật sự nên dùng

Lệnh return mid sớm trong template kinh điển là một điểm yếu. Khi có phần tử trùng lặp nó trả về một chỉ số khớp bất kỳ, hiếm khi là thứ bạn muốn, và nó không trả lời được câu “phần tử này sẽ nằm ở đâu nếu tôi chèn vào?”. Các template tìm biên dạng nửa mở hữu dụng hơn hẳn và ít bẫy hơn.

• lower_bound(arr, x) — chỉ số của phần tử đầu tiên ≥ x. Tương đương: có bao nhiêu phần tử nhỏ hơn hẳn x; tương đương: vị trí trái nhất mà x có thể chèn vào mà vẫn giữ array đã sắp.
• upper_bound(arr, x) — chỉ số của phần tử đầu tiên > x. Vị trí chèn phải nhất tương ứng.

def lower_bound(arr, target):
    """Chỉ số i đầu tiên có arr[i] >= target; bằng len(arr) nếu không có.
    Bất biến: đáp án luôn nằm trong khoảng NỬA MỞ [lo, hi)."""
    lo, hi = 0, len(arr)               # hi là biên MỞ — chú ý: len(arr), không phải len(arr)-1
    while lo < hi:                     # [lo, hi) rỗng khi lo == hi
        mid = lo + (hi - lo) // 2      # lo <= mid < hi, nên mid luôn là chỉ số hợp lệ
        if arr[mid] < target:
            lo = mid + 1               # arr[mid] quá nhỏ: nó và mọi thứ bên trái
        else:                          # đều bị loại
            hi = mid                   # arr[mid] CÓ THỂ là đáp án: giữ lại trong khoảng
    return lo                          # lo == hi: chính là biên


def upper_bound(arr, target):
    """Chỉ số i đầu tiên có arr[i] > target; bằng len(arr) nếu không có."""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:         # khác biệt DUY NHẤT so với lower_bound: <= thay vì <
            lo = mid + 1
        else:
            hi = mid
    return lo

Mọi thứ khác đều suy ra từ hai hàm này, không cần thêm binary search nào nữa để mà viết sai:

a = [1, 3, 3, 3, 7, 9]

lower_bound(a, 3)                     # 1  — chỉ số đầu tiên của 3
upper_bound(a, 3)                     # 4  — ngay sau chỉ số cuối cùng của 3
upper_bound(a, 3) - lower_bound(a, 3) # 3  — có bao nhiêu số 3 (0 nghĩa là "không có")
lower_bound(a, 5)                     # 4  — vị trí chèn cho một giá trị không tồn tại
upper_bound(a, 3) - 1                 # 3  — chỉ số cuối cùng của 3
lower_bound(a, 4) - 1                 # 3  — predecessor: phần tử cuối cùng < 4
lower_bound(a, 4)                     # 4  — successor: phần tử đầu tiên >= 4


def contains(a, x):
    """Kiểm tra thành viên dựa trên lower_bound — chú ý phải kiểm tra biên trước."""
    i = lower_bound(a, x)
    return i < len(a) and a[i] == x

Trace của lower_bound([1, 3, 5, 7, 9, 11, 13], 7):

Bước	lo	hi	mid	arr[mid]	arr[mid] < 7?	Hành động
1	0	7	3	7	Không	hi = 3
2	0	3	1	3	Có	lo = 2
3	2	3	2	5	Có	lo = 3
4	3	3	—	—	—	lo == hi → return 3

Và của lower_bound(arr, 8) — giá trị không tồn tại:

Bước	lo	hi	mid	arr[mid]	arr[mid] < 8?	Hành động
1	0	7	3	7	Có	lo = 4
2	4	7	5	11	Không	hi = 5
3	4	5	4	9	Không	hi = 4
4	4	4	—	—	—	return 4 (vị trí chèn)

Hãy để ý trường hợp “không tìm thấy” trả về một thứ có ích thay vì -1: vị trí mà giá trị đó thuộc về.

Điểm danh các cái bẫy off-by-one

Cái bẫy	Triệu chứng	Cách sửa
hi = len(arr) với template biên đóng	IndexError, hoặc bỏ sót phần tử cuối	Biên đóng → len(arr) - 1; nửa mở → len(arr) — đừng bao giờ trộn lẫn
while lo < hi với template biên đóng	Khoảng một phần tử không bao giờ được kiểm tra	Dùng while lo <= hi với biên đóng
lo = mid thay vì lo = mid + 1	Vòng lặp vô hạn khi hi == lo + 1 (vì mid làm tròn xuống thành lo)	Loại mid ở phía đã bị loại trừ, hoặc làm tròn mid lên
(lo + hi) // 2 trong ngôn ngữ số nguyên độ rộng cố định	Kết quả sai âm thầm trên array > 2³⁰	lo + (hi - lo) // 2
while hi - lo > eps với số thực	Không kết thúc khi eps nhỏ hơn độ phân giải float	Lặp một số lần cố định (~100) thay vì vậy
Tìm kiếm trên array chưa sắp	Kết quả sai âm thầm, không báo lỗi	Assert hoặc ghi rõ điều kiện tiên quyết

Cái bẫy lo = mid xứng đáng có template riêng, vì bài toán “tìm vị trí cuối cùng mà predicate còn đúng” thật sự cần nó:

def last_true(lo, hi, pred):
    """x lớn nhất trong [lo, hi] có pred(x) đúng, giả định pred có dạng
    true, true, ..., true, false, ..., false. Trả về lo - 1 nếu không có."""
    lo -= 1                            # lo - 1 biểu diễn "không có đáp án hợp lệ"
    while lo < hi:
        # Làm tròn LÊN. Với `(lo + hi) // 2`, trường hợp hi == lo + 1 cho mid == lo,
        # và `lo = mid` không làm lo thay đổi — vòng lặp vô hạn.
        mid = lo + (hi - lo + 1) // 2
        if pred(mid):
            lo = mid                   # mid thỏa: nó là ứng viên, giữ lại
        else:
            hi = mid - 1               # mid không thỏa: loại nó ra
    return lo

bisect của Python — thứ bạn dùng trên production

Thư viện chuẩn cài đặt đúng lower_bound và upper_bound, bằng C, với bug đã được gỡ sẵn.

import bisect

a = [1, 3, 3, 3, 7, 9]

bisect.bisect_left(a, 3)      # 1  — lower_bound
bisect.bisect_right(a, 3)     # 4  — upper_bound  (bisect.bisect là alias)
bisect.bisect_right(a, 3) - bisect.bisect_left(a, 3)   # 3 lần xuất hiện

# insort giữ cho list luôn được sắp xếp. Phần TÌM KIẾM là O(log n) nhưng phần CHÈN
# là O(n), vì chèn vào list phải đẩy mọi phần tử phía sau. Chấp nhận được khi thỉnh
# thoảng mới chèn vào list vừa phải; dùng balanced tree hoặc heap cho luồng ghi nóng.
bisect.insort(a, 5)           # a == [1, 3, 3, 3, 5, 7, 9]

# Từ Python 3.10, `key=` giúp tránh phải dựng một list sort key song song.
records = [("a", 1), ("b", 3), ("c", 7)]
i = bisect.bisect_left(records, 3, key=lambda r: r[1])   # 1

# lo/hi giới hạn phạm vi tìm kiếm về một lát cắt mà không cần copy nó
bisect.bisect_left(a, 5, lo=2, hi=6)

Idiom kinh điển của bisect là phân loại một giá trị liên tục vào các hạng mục có thứ tự — rẻ hơn và rõ hơn một chuỗi if/elif:

def grade(score, breakpoints=(60, 70, 80, 90), letters="FDCBA"):
    """O(log k) thay vì O(k) phép so sánh, và bảng phân loại là dữ liệu chứ không phải code."""
    return letters[bisect.bisect_right(breakpoints, score)]


assert [grade(s) for s in (33, 65, 77, 89, 95)] == ["F", "D", "C", "B", "A"]

Binary search trên đáp án

Đây là kỹ thuật biến binary search thành một công cụ giải bài toán chứ không chỉ là một thao tác trên array. Bỏ array sang một bên: thứ mà binary search thật sự cần là

một không gian tìm kiếm có thứ tự, và một monotonic predicate pred(x) trên nó — false, false, …, false, true, true, …, true.

Có được điều đó, O(log n) lần đánh giá pred sẽ tìm ra biên. Phiên bản trên array chỉ là trường hợp riêng pred(i) = (arr[i] >= target), đơn điệu vì array đã được sắp xếp.

def first_true(lo, hi, pred):
    """x nhỏ nhất trong khoảng nửa mở [lo, hi) có pred(x) đúng.
    Giả định pred đơn điệu: false ... false, true ... true.
    Trả về hi nếu pred sai ở mọi nơi."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if pred(mid):
            hi = mid                   # mid có thể là biên — giữ lại
        else:
            lo = mid + 1               # mid sai — loại ra
    return lo


# Việc tìm kiếm trên array giờ chỉ còn một dòng trên cùng một hàm nguyên thủy:
def lower_bound_via_pred(arr, target):
    return first_true(0, len(arr), lambda i: arr[i] >= target)

Đòn bẩy đến từ những bài toán mà đáp án là một con số, việc kiểm tra một đáp án ứng viên thì dễ, còn tìm trực tiếp thì khó:

def min_ship_capacity(weights, days):
    """Sức chứa tàu nhỏ nhất chở được toàn bộ kiện hàng, đúng thứ tự đó,
    trong vòng `days` ngày. Cách ngây thơ là thử từng sức chứa một."""

    def feasible(cap):
        """Kiểm tra kiểu greedy: với sức chứa `cap` thì mất bao nhiêu ngày?
        O(n) — và dễ viết đúng, đó chính là điều quan trọng."""
        needed, load = 1, 0
        for w in weights:
            if load + w > cap:
                needed += 1
                load = 0
            load += w
        return needed <= days

    # Đơn điệu: nếu sức chứa c khả thi thì mọi sức chứa > c cũng khả thi.
    # Cận dưới của không gian tìm kiếm: ít nhất phải chứa được kiện nặng nhất.
    # Cận trên: chở tất cả cùng lúc thì luôn xong trong một ngày.
    return first_true(max(weights), sum(weights) + 1, feasible)


assert min_ship_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days=5) == 15

Chi phí là O(log(range) · cost(pred)) — ở đây là O(n log(sum(weights))), với một triệu kiện hàng thì tương đương khoảng 20–50 lần chạy một vòng quét tuyến tính. Các hình dáng bài toán lặp đi lặp lại:

• “Cực tiểu hóa giá trị lớn nhất” / “cực đại hóa giá trị nhỏ nhất” — cách diễn đạt này gần như chắc chắn là tín hiệu đáp án có thể binary search được. (Tổng lớn nhất nhỏ nhất khi chia đoạn, khoảng cách nhỏ nhất lớn nhất giữa các vật được đặt, thời gian nhỏ nhất để hoàn thành với k công nhân.)
• Bài toán tốc độ / nhịp độ — “tốc độ chậm nhất mà công việc vẫn kịp hoàn thành”. Kiểm tra tính khả thi ở một tốc độ chỉ là một mô phỏng đơn giản.
• Phân bổ tài nguyên — “sức chứa / ngân sách / số máy nhỏ nhất mà vẫn đủ”.

Hai biến thể xuất hiện liên tục:

def integer_sqrt(n):
    """x lớn nhất có x*x <= n. `x*x > n` là đơn điệu theo x."""
    return first_true(0, n + 2, lambda x: x * x > n) - 1


assert [integer_sqrt(k) for k in (0, 1, 15, 16, 17, 10**18)] == [0, 1, 3, 4, 4, 10**9]


def sqrt_float(n):
    """Binary search trên khoảng liên tục. Đừng bao giờ lặp theo `hi - lo > eps`:
    khi xuống dưới độ phân giải của float, điều kiện đó không bao giờ sai được nữa.
    Hãy lặp một số lần cố định — 100 lần chia đôi đã vượt xa độ chính xác double."""
    lo, hi = 0.0, max(1.0, float(n))
    for _ in range(100):
        mid = (lo + hi) / 2
        if mid * mid < n:
            lo = mid
        else:
            hi = mid
    return lo

Danh sách kiểm tra trước khi áp dụng: predicate có thật sự đơn điệu không? Nếu pred đúng, rồi sai, rồi lại đúng, binary search sẽ trả về một biên tùy ý và bạn nhận về một đáp án sai trông rất thuyết phục. Hãy chứng minh tính đơn điệu, hoặc chí ít kiểm tra bằng brute force trên input nhỏ rồi đối chiếu với kết quả binary search — phép kiểm tra đối chiếu đó bắt được gần như mọi sai lầm của kỹ thuật này.

Vài thuật toán tìm kiếm liên quan đáng biết

Thuật toán	Độ phức tạp	Khi nào dùng
Exponential (galloping) search	O(log i) với i là chỉ số của đáp án	Dữ liệu đã sắp nhưng không giới hạn hoặc dạng stream, hoặc khi target nằm gần đầu: nhân đôi biên cho tới khi vượt qua, rồi binary search trong [b/2, b]. Được dùng bên trong bước merge của Timsort.
Interpolation search	Trung bình O(log log n), worst case O(n)	Key số phân bố đều — đoán vị trí từ giá trị thay vì luôn lấy điểm giữa. Suy giảm rất tệ với dữ liệu lệch.
Ternary search	O(log n)	Tìm cực trị của một hàm unimodal, không phải trên array đã sắp.
Binary search trên array xoay vòng	O(log n)	Một trong hai nửa của phép chia luôn đã sắp; xác định nửa nào rồi áp dụng phép kiểm tra thông thường.
BFS / DFS	O(V + E)	Tìm kiếm trên tree hoặc graph chứ không phải tập tuyến tính — ./10-tree-data-structures.md, ./13-graph-data-structures.md.

Bảng tổng hợp độ phức tạp

Cách tiếp cận	Tiền xử lý	Tìm kiếm	Chèn	Bộ nhớ	Thao tác có thứ tự (range, min/max, successor)
Linear search, array chưa sắp	không	O(n)	O(1) amortized	O(n)	O(n)
Binary search, array đã sắp	sort O(n log n)	O(log n)	O(n) (phải dịch)	O(n)	O(log n + k)
Hash table	không	O(1) TB, O(n) worst	O(1) amortized	O(n), gấp ~2–3 lần dữ liệu thô	O(n log n) — phải sort
Balanced BST / skip list	không	O(log n)	O(log n)	O(n) + chi phí node	O(log n + k)
B-tree (trên đĩa)	không	O(log_B n) — rất ít I/O	O(log_B n)	O(n)	O(log_B n + k)

Khi nào array đã sắp + binary search thắng hash table

O(log n) so với O(1) khiến hash table trông như bất khả chiến bại, nên rất đáng nói cụ thể về rất nhiều trường hợp mà nó không phải vậy.

• Range query. “Mọi key giữa a và b” là một lần lower_bound(a) rồi đi tuyến tính — O(log n + k). Hash table phải quét tất cả, O(n). Riêng lý do này là vì sao B-tree index trong database áp đảo hash index: chúng phục vụ equality lẫn range lẫn ORDER BY từ cùng một cấu trúc (../../postgresql-dba/vi/08-indexing-strategies.md, ./18-indexing.md).
• Predecessor / successor / gần nhất. “Key lớn nhất ≤ x” chỉ là một lần gọi bisect. Hash table hoàn toàn không trả lời được nếu không quét toàn bộ. Các truy vấn theo timestamp (“phiên bản config có hiệu lực tại thời điểm T”, “khung giá cho số tiền này”) chính là dạng truy vấn này.
• Order statistics và duyệt theo thứ tự. Min, max, trung vị, “100 phần tử nhỏ nhất”, “duyệt theo thứ tự” đều là O(1) hoặc một lát cắt trên array đã sắp, còn với hash table thì lần nào cũng cần một lần sort O(n log n).
• Bộ nhớ. Một array('q') đã sắp chứa một triệu số nguyên 64-bit tốn 8 MB. Cùng dữ liệu đó trong set của Python tốn khoảng 30–60 MB, do phần dư dành cho hashing (bảng cố ý được giữ trống một phần ba) và chi phí mỗi object. Khi tập dữ liệu làm việc phải nằm vừa cache hoặc trong một tiến trình bị giới hạn, hệ số 5 lần này quan trọng hơn hệ số 20 lần ở chi phí lookup.
• Dữ liệu chỉ đọc, dựng một lần. Một bảng tra cứu tĩnh — danh sách từ được biên dịch sẵn, bảng định tuyến, một file index đã sắp — có thể mmap thẳng từ đĩa và binary search luôn, không cần deserialize gì cả. Hash table phải được dựng lại trong bộ nhớ trước lần lookup đầu tiên. Đây là lý do các định dạng index trên đĩa là array đã sắp hoặc B-tree, không bao giờ là hash table.
• Cache locality khi n nhỏ. Với vài trăm phần tử, một array đã sắp nằm gọn trong một hai cache line cạnh tranh ngang hoặc nhanh hơn một lần hash lookup, vì hash lookup tốn một lần tính hash cộng một lần truy cập bộ nhớ ngẫu nhiên, còn tìm kiếm trên array thì vẫn nằm trong cache.
• Key đắt để hash. Hash một chuỗi dài phải đọc toàn bộ chuỗi. Một phép so sánh trong binary search thường phân kỳ ngay ở vài byte đầu. Với key rất dài, O(log n) phép so sánh rẻ có thể thắng một lần hash đắt.
• Worst case dự đoán được. Binary search luôn là O(log n). Hash table là O(n) với key mang tính đối kháng — tấn công hash flooding mô tả trong ./07-hash-tables.md. Ở nơi kẻ tấn công kiểm soát key và tail latency quan trọng, bảo đảm tất định này đáng để trả giá.
• Xử lý phần tử trùng lặp. upper_bound - lower_bound đếm số lần xuất hiện trong O(log n) và cho bạn nguyên cả cụm dưới dạng một lát cắt liền kề. Một hash multimap cần một list riêng cho mỗi key.

Ngược lại, hash table thắng áp đảo khi: lookup thuần túy là kiểm tra bằng nhau, dữ liệu thay đổi thường xuyên (chèn vào array đã sắp là O(n)), key không có thứ tự tự nhiên, hoặc n đủ lớn để log n ≈ 20+ phép so sánh thật sự đắt hơn một lần hash. Thú thật thì đó là phần lớn thời gian — nên nó mới là lựa chọn mặc định. Vấn đề là nhận ra những trường hợp còn lại.

Vùng trung gian, khi bạn cần cả truy vấn có thứ tự lẫn cập nhật rẻ, là balanced BST, skip list (./11-balanced-and-multiway-trees.md), hoặc — trong Python, nơi không có sẵn thứ nào trong số đó — thư viện bên thứ ba sortedcontainers, đạt được O(log n) trên thực tế cho thao tác chèn bằng cách dùng list lồng list thay vì tree.

Best Practices

• Chọn một template binary search duy nhất và đừng bao giờ ứng biến. Dạng nửa mở lower_bound / first_true là dạng đáng thuộc lòng: không có return sớm, không có mid ± 1 ở cả hai phía, và nó cho thông tin hữu ích khi target không tồn tại. Mọi biến thể khác đều dựng được từ nó.
• Viết bất biến vào comment ngay trên vòng lặp. “Đáp án nằm trong [lo, hi)” không phải trang trí — nó chính là thứ cho bạn biết nên cập nhật thành mid hay mid + 1.
• Luôn trace bằng tay các trường hợp rỗng, một phần tử, và hai phần tử. Mọi lỗi off-by-one đều nằm ở đó, và ba dòng trace bằng tay rẻ hơn một giờ trong debugger (./01-programming-fundamentals-and-pseudocode.md).
• Dùng bisect trong Python thay vì tự viết. Nó là code C, nó đúng, và bisect_left/bisect_right chính là lower_bound/upper_bound. Hãy nhớ cái nào là cái nào — bisect trần là bisect_right, điều khiến nhiều người bất ngờ.
• Nhớ rằng bisect.insort là O(n). Phần tìm kiếm là logarit, phần chèn vào list thì không. Dựng một list đã sắp bằng insort trong vòng lặp là O(n²); thu thập rồi sort một lần là O(n log n).
• Cứ viết lo + (hi - lo) // 2 kể cả trong Python. Nó chẳng tốn gì và là thói quen giữ cho cùng đoạn code đó vẫn đúng khi bạn viết bằng Go hay Java.
• Đừng bao giờ binary search trên linked list. Đi tới điểm giữa tốn O(n), khiến cả lần tìm kiếm thành O(n) với hằng số nhân tệ hơn một lần quét thường. Random access là điều kiện tiên quyết, không phải tiện nghi.
• Đừng binary search dưới ~50 phần tử nếu chưa đo đạc. Quét tuyến tính trên array liền kề thường nhanh hơn ở kích thước đó, và đơn giản hơn.
• Kiểm chứng tính đơn điệu trước khi binary search trên đáp án. Brute force các trường hợp nhỏ rồi đối chiếu với kết quả binary search; một predicate không đơn điệu sẽ cho ra đáp án sai một cách tự tin, chứ không báo lỗi.
• Giới hạn số vòng lặp khi tìm kiếm trên số thực. Một số lần lặp cố định (khoảng 100) sẽ kết thúc; while hi - lo > eps thì có thể không.
• Sort một lần, tìm kiếm nhiều lần. Trả O(n log n) một lần (./08-sorting-algorithms.md) để đổi lấy lookup O(log n) là đáng từ truy vấn thứ hai hoặc thứ ba trở đi. Với một lần lookup duy nhất trên dữ liệu sẽ bỏ đi, cứ quét thôi.
• Chọn cấu trúc dựa trên hỗn hợp các loại truy vấn, không chỉ dựa vào độ phức tạp lookup. Chỉ equality và ghi nhiều → hash table. Range, thứ tự, hoặc dataset tĩnh chủ yếu đọc → array đã sắp. Cần cả hai, ghi nhiều → balanced tree.

Tài liệu tham khảo

• roadmap.sh — Data Structures & Algorithms
• Binary search algorithm — Wikipedia
• Linear search — Wikipedia
• CLRS — Introduction to Algorithms (binary search, searching)
• Python Documentation — bisect — Array bisection algorithm
• cp-algorithms — Binary search
• Google Research blog — “Nearly All Binary Searches and Mergesorts are Broken” (Joshua Bloch, 2006)
• std::lower_bound / std::upper_bound — cppreference
• Exponential search — Wikipedia
• Interpolation search — Wikipedia
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• Big-O Cheat Sheet
• VisuAlgo — Binary Search (in Sorting/Searching visualizations)

def linear_search(arr, target):
    """Return the index of the first occurrence of target, or -1. O(n)."""
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

search for 8 in [1, 3, 5, 7, 9, 11, 13]

step 1:  1   3   5  [7]  9  11  13     mid = 7,  7 < 8  → drop the left half and mid
step 2:                  9 [11] 13     mid = 11, 11 > 8 → drop 11 and everything right
step 3:                 [9]            mid = 9,  9 > 8  → drop it
step 4:                 (empty)        → not found; 8 belongs at index 4

def binary_search(arr, target):
    """Return an index of target in the sorted list arr, or -1 if absent.
    Invariant: if target is in arr, its index lies in the CLOSED range [lo, hi]."""
    lo, hi = 0, len(arr) - 1           # hi is INCLUSIVE
    while lo <= hi:                    # [lo, hi] is non-empty while lo == hi
        mid = lo + (hi - lo) // 2      # same as (lo + hi) // 2, without overflow
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1               # mid is too small — exclude it
        else:
            hi = mid - 1               # mid is too large — exclude it
    return -1                          # lo > hi: the range is empty

def lower_bound(arr, target):
    """First index i with arr[i] >= target; len(arr) if there is none.
    Invariant: the answer always lies in the HALF-OPEN range [lo, hi)."""
    lo, hi = 0, len(arr)               # hi is EXCLUSIVE — note: len(arr), not len(arr)-1
    while lo < hi:                     # [lo, hi) is empty when lo == hi
        mid = lo + (hi - lo) // 2      # lo <= mid < hi, so mid is always a valid index
        if arr[mid] < target:
            lo = mid + 1               # arr[mid] is too small: it and everything
        else:                          # to its left are excluded
            hi = mid                   # arr[mid] may BE the answer: keep it in range
    return lo                          # lo == hi: the boundary


def upper_bound(arr, target):
    """First index i with arr[i] > target; len(arr) if there is none."""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:         # the ONLY difference from lower_bound: <= vs <
            lo = mid + 1
        else:
            hi = mid
    return lo

a = [1, 3, 3, 3, 7, 9]

lower_bound(a, 3)                     # 1  — first index of 3
upper_bound(a, 3)                     # 4  — one past the last index of 3
upper_bound(a, 3) - lower_bound(a, 3) # 3  — how many 3s (0 means "absent")
lower_bound(a, 5)                     # 4  — insertion point for a missing value
upper_bound(a, 3) - 1                 # 3  — last index of 3
lower_bound(a, 4) - 1                 # 3  — predecessor: last element < 4
lower_bound(a, 4)                     # 4  — successor: first element >= 4


def contains(a, x):
    """Membership test built on lower_bound — note the bounds check first."""
    i = lower_bound(a, x)
    return i < len(a) and a[i] == x

def last_true(lo, hi, pred):
    """Largest x in [lo, hi] with pred(x) true, assuming pred is
    true, true, ..., true, false, ..., false. Returns lo - 1 if none."""
    lo -= 1                            # lo - 1 represents "no valid answer"
    while lo < hi:
        # Round UP. With `(lo + hi) // 2`, the case hi == lo + 1 gives mid == lo,
        # and `lo = mid` leaves lo unchanged — an infinite loop.
        mid = lo + (hi - lo + 1) // 2
        if pred(mid):
            lo = mid                   # mid works: it is a candidate, keep it
        else:
            hi = mid - 1               # mid fails: exclude it
    return lo

import bisect

a = [1, 3, 3, 3, 7, 9]

bisect.bisect_left(a, 3)      # 1  — lower_bound
bisect.bisect_right(a, 3)     # 4  — upper_bound  (bisect.bisect is an alias)
bisect.bisect_right(a, 3) - bisect.bisect_left(a, 3)   # 3 occurrences

# insort keeps a list sorted. The SEARCH is O(log n) but the INSERT is O(n),
# because a list insertion shifts every following element. Fine for occasional
# inserts into a modest list; use a balanced tree or a heap for a hot write path.
bisect.insort(a, 5)           # a == [1, 3, 3, 3, 5, 7, 9]

# Since Python 3.10, `key=` avoids building a parallel list of sort keys.
records = [("a", 1), ("b", 3), ("c", 7)]
i = bisect.bisect_left(records, 3, key=lambda r: r[1])   # 1

# lo/hi restrict the search to a slice without copying it
bisect.bisect_left(a, 5, lo=2, hi=6)

def grade(score, breakpoints=(60, 70, 80, 90), letters="FDCBA"):
    """O(log k) instead of O(k) comparisons, and the table is data, not code."""
    return letters[bisect.bisect_right(breakpoints, score)]


assert [grade(s) for s in (33, 65, 77, 89, 95)] == ["F", "D", "C", "B", "A"]

def first_true(lo, hi, pred):
    """Smallest x in the half-open range [lo, hi) with pred(x) true.
    Assumes pred is monotonic: false ... false, true ... true.
    Returns hi if pred is false everywhere."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if pred(mid):
            hi = mid                   # mid might be the boundary — keep it
        else:
            lo = mid + 1               # mid is false — discard it
    return lo


# The array search is now a one-liner over the same primitive:
def lower_bound_via_pred(arr, target):
    return first_true(0, len(arr), lambda i: arr[i] >= target)

def min_ship_capacity(weights, days):
    """Smallest ship capacity that can carry all packages, in the given order,
    within `days` days. Naively you would search capacities one at a time."""

    def feasible(cap):
        """Greedy check: with capacity `cap`, how many days does it take?
        O(n) — and easy to get right, which is the whole point."""
        needed, load = 1, 0
        for w in weights:
            if load + w > cap:
                needed += 1
                load = 0
            load += w
        return needed <= days

    # Monotonic: if capacity c is feasible, every capacity > c is too.
    # Lower bound of the search space: we must at least fit the heaviest package.
    # Upper bound: carrying everything at once always finishes in one day.
    return first_true(max(weights), sum(weights) + 1, feasible)


assert min_ship_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days=5) == 15

def integer_sqrt(n):
    """Largest x with x*x <= n. `x*x > n` is monotonic in x."""
    return first_true(0, n + 2, lambda x: x * x > n) - 1


assert [integer_sqrt(k) for k in (0, 1, 15, 16, 17, 10**18)] == [0, 1, 3, 4, 4, 10**9]


def sqrt_float(n):
    """Binary search on a continuous range. Never loop on `hi - lo > eps`:
    below float resolution that condition can never become false. Loop a fixed
    number of times instead — 100 halvings is far past double precision."""
    lo, hi = 0.0, max(1.0, float(n))
    for _ in range(100):
        mid = (lo + hi) / 2
        if mid * mid < n:
            lo = mid
        else:
            hi = mid
    return lo