Binary Search — Tìm kiếm nhị phân

Jon Bentley — tác giả cuốn "Programming Pearls" — từng giao bài binary search cho các lập trình viên chuyên nghiệp. Kết quả: 90% viết sai. Không phải họ không hiểu ý tưởng — chia đôi, so sánh, lặp lại. Vấn đề nằm ở off-by-one: < hay <=? mid + 1 hay mid? right = n hay right = n - 1? Sai một ký tự, thuật toán hoặc bỏ sót phần tử, hoặc lặp vô hạn.

Thực tế còn tệ hơn. Hàm binarySearch trong Java standard library tồn tại bug integer overflow suốt 9 năm (2002-2011) ở dòng int mid = (low + high) / 2. Khi low + high vượt Integer.MAX_VALUE, mid trở thành số âm — crash. Bug này ẩn trong production code của hàng triệu ứng dụng Java.

Binary search không khó ở concept. Nó khó ở chi tiết triển khai, và đó chính xác là thứ bài viết này sẽ giải quyết.

Bức tranh tư duy

Hình dung bạn cần tìm một từ trong từ điển giấy 1000 trang. Bạn không lật từ trang 1 — bạn mở giữa cuốn (~trang 500). Từ cần tìm bắt đầu bằng "T" nhưng trang 500 đang ở chữ "M"? Bạn biết "T" nằm nửa sau → bỏ hẳn 500 trang đầu. Mở giữa nửa còn lại (~trang 750). Lần này chữ "S" → vẫn trước "T" → bỏ thêm 250 trang. Cứ thế, sau ~10 lần lật, bạn tìm đúng trang.

text

Mảng sorted: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]    target = 13

Bước 1: lo=0, hi=9, mid=4  → arr[4]=9  < 13 → lo=5
         [1  3  5  7  9 |11  13  15  17  19]
                         ^^^ bỏ nửa trái

Bước 2: lo=5, hi=9, mid=7  → arr[7]=15 > 13 → hi=6
         [11  13  15 |17  19]
                      ^^^ bỏ nửa phải

Bước 3: lo=5, hi=6, mid=5  → arr[5]=11 < 13 → lo=6
         [11 |13]
          ^^^ bỏ bên trái

Bước 4: lo=6, hi=6, mid=6  → arr[6]=13 == 13 → TÌM THẤY!

Từ 10 phần tử, chỉ cần 4 bước. Từ 1 triệu phần tử? Chỉ ~20 bước. Từ 1 tỷ? ~30 bước. Đó là sức mạnh của O(log n).

📌 Khi nào analogy bị phá vỡ

Từ điển giấy cho phép bạn "ước lượng" vị trí dựa trên chữ cái (mở gần cuối cho chữ "T"). Đó là interpolation search, không phải binary search. Binary search thuần túy luôn mở chính giữa, không đoán.

Cốt lõi kỹ thuật

Tìm giá trị chính xác — Iterative

Template chuẩn nhất, an toàn nhất. Ba điểm cần khắc ghi: lo <= hi (không phải <), mid = lo + (hi - lo) / 2 (tránh overflow), cập nhật lo = mid + 1 hoặc hi = mid - 1 (không phải mid).

C++PythonJavaGo

cpp

int binarySearch(const int arr[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

python

def binary_search(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

java

public static int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

func binarySearch(arr []int, target int) int {
    lo, hi := 0, len(arr)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

Tìm giá trị chính xác — Recursive

Cùng logic, dạng đệ quy. Ít dùng trong production vì tốn stack frame O(log n), nhưng cần biết cho phỏng vấn.

C++PythonJavaGo

cpp

int binarySearchRec(const int arr[], int lo, int hi, int target) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binarySearchRec(arr, mid + 1, hi, target);
    return binarySearchRec(arr, lo, mid - 1, target);
}

python

def binary_search_rec(arr: list[int], lo: int, hi: int, target: int) -> int:
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, mid + 1, hi, target)
    else:
        return binary_search_rec(arr, lo, mid - 1, target)

java

public static int binarySearchRec(int[] arr, int lo, int hi, int target) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binarySearchRec(arr, mid + 1, hi, target);
    return binarySearchRec(arr, lo, mid - 1, target);
}

func binarySearchRec(arr []int, lo, hi, target int) int {
    if lo > hi {
        return -1
    }
    mid := lo + (hi-lo)/2
    if arr[mid] == target {
        return mid
    } else if arr[mid] < target {
        return binarySearchRec(arr, mid+1, hi, target)
    }
    return binarySearchRec(arr, lo, mid-1, target)
}

Lower Bound — Tìm vị trí trái nhất (≥ target)

Trả về index đầu tiên mà arr[index] >= target. Nếu target lớn hơn mọi phần tử, trả về n. Đây là std::lower_bound trong C++ và bisect_left trong Python.

Chú ý sự khác biệt: hi = n (không phải n - 1), lo < hi (không phải <=), và hi = mid (không phải mid - 1).

C++PythonJavaGo

cpp

int lowerBound(const int arr[], int n, int target) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

python

def lower_bound(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo

java

public static int lowerBound(int[] arr, int target) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

func lowerBound(arr []int, target int) int {
    lo, hi := 0, len(arr)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if arr[mid] >= target {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

Upper Bound — Tìm vị trí phải nhất (> target)

Trả về index đầu tiên mà arr[index] > target. Kết hợp lower_bound và upper_bound cho phép đếm số lần xuất hiện: count = upperBound(target) - lowerBound(target).

C++PythonJavaGo

cpp

int upperBound(const int arr[], int n, int target) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

python

def upper_bound(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] > target:
            hi = mid
        else:
            lo = mid + 1
    return lo

java

public static int upperBound(int[] arr, int target) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

func upperBound(arr []int, target int) int {
    lo, hi := 0, len(arr)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if arr[mid] > target {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

Parametric Search — Binary search trên đáp án

Không phải lúc nào binary search cũng tìm phần tử trong mảng. Kỹ thuật mạnh nhất là binary search trên không gian đáp án: nếu bài toán hỏi "giá trị nhỏ nhất/lớn nhất thỏa mãn điều kiện gì đó" và hàm kiểm tra có tính monotonic (false...false...true...true), bạn binary search trên đáp án.

python

def parametric_search(lo: int, hi: int, condition) -> int:
    """Tìm giá trị nhỏ nhất x trong [lo, hi] sao cho condition(x) = True.
    Yêu cầu: condition(x) monotonic — False...False...True...True."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if condition(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Ví dụ kinh điển: "Chia mảng thành k nhóm liên tiếp sao cho tổng nhóm lớn nhất là nhỏ nhất." Đây không phải tìm phần tử — mà binary search trên giá trị "tổng nhóm lớn nhất", kiểm tra xem có thể chia thành ≤ k nhóm với giới hạn đó không.

Binary Search trên số thực

Khi tìm kiếm trên miền liên tục (ví dụ: tìm căn bậc hai), thay vì lo < hi dùng hi - lo > epsilon hoặc lặp cố định số lần.

python

def sqrt_binary_search(x: float, epsilon: float = 1e-9) -> float:
    """Tìm căn bậc hai bằng binary search trên số thực."""
    if x < 0:
        raise ValueError("Không tồn tại căn bậc hai của số âm")
    lo, hi = 0.0, max(1.0, x)
    for _ in range(100):  # 100 iterations đạt precision ~10⁻³⁰
        mid = (lo + hi) / 2
        if mid * mid <= x:
            lo = mid
        else:
            hi = mid
    return lo

Tại sao lặp cố định thay vì epsilon?

Với floating point, hi - lo > epsilon có thể không hội tụ nếu epsilon quá nhỏ so với giá trị lo, hi (do precision loss). Lặp 100 lần luôn an toàn — mỗi lần chia đôi, precision tăng 1 bit → 100 lần = ~10⁻³⁰.

Thực chiến

Tình huống: Tìm phiên bản lỗi đầu tiên (First Bad Version)

Bối cảnh: CI/CD pipeline của team có 1000 builds. Từ một build nào đó trở đi, test bắt đầu fail. Mỗi lần chạy test mất 5 phút. Cần tìm build đầu tiên bị lỗi nhanh nhất có thể.

Mục tiêu: Tìm first_bad sao cho is_bad(first_bad) = True và is_bad(first_bad - 1) = False. Giảm thiểu số lần gọi is_bad().

python

def first_bad_version(n: int, is_bad) -> int:
    """Binary search tìm version lỗi đầu tiên.
    is_bad(version) trả True/False — monotonic: FFFF...TTTT.
    """
    lo, hi = 1, n
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_bad(mid):
            hi = mid      # mid có thể là bad đầu tiên
        else:
            lo = mid + 1  # mid chắc chắn không phải
    return lo

Phân tích:

Đây chính là lower_bound pattern. Thay vì linear scan 1000 builds (83 giờ), binary search chỉ cần ~10 lần chạy test (50 phút). Lưu ý dùng lo < hi (không phải <=) và hi = mid (không phải mid - 1) vì mid có thể chính là đáp án.

Tình huống: Tìm kiếm trong mảng sorted đã bị xoay (Rotated Sorted Array)

Bối cảnh: Hệ thống log circular buffer lưu timestamps theo thứ tự tăng dần, nhưng bị wrap-around. Mảng [4, 5, 6, 7, 0, 1, 2] — ban đầu sorted [0,1,2,4,5,6,7], bị xoay tại index 4.

python

def search_rotated(nums: list[int], target: int) -> int:
    """Binary search trên mảng sorted đã xoay — O(log n)."""
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid

        # Xác định nửa nào đang sorted
        if nums[lo] <= nums[mid]:
            # Nửa trái sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # Nửa phải sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Phân tích:

Trick then chốt: trong mảng rotated, luôn có ít nhất một nửa đang sorted. Kiểm tra nửa nào sorted bằng nums[lo] <= nums[mid], rồi quyết định target nằm ở nửa nào. Từ đó loại bỏ nửa còn lại. Vẫn giữ O(log n).

Sai lầm điển hình

❌ Sai lầm 1: Integer overflow khi tính mid

Vấn đề: Bug kinh điển tồn tại 9 năm trong Java standard library.

java

// SAI: overflow khi lo + hi > Integer.MAX_VALUE
int mid = (lo + hi) / 2;

Tại sao sai: Với lo = 2_000_000_000 và hi = 2_000_000_000, tổng lo + hi = 4_000_000_000 vượt Integer.MAX_VALUE (2,147,483,647). Kết quả: mid trở thành số âm, access arr[mid] gây ArrayIndexOutOfBoundsException. Bug này chỉ xảy ra trên mảng lớn — hoàn toàn invisible trong unit test nhỏ.

java

// ĐÚNG: tránh overflow bằng phép trừ
int mid = lo + (hi - lo) / 2;
// Hoặc dùng unsigned right shift (Java-specific)
int mid = (lo + hi) >>> 1;

❌ Sai lầm 2: Nhầm điều kiện vòng lặp — `<` vs `<=`

Vấn đề: Dùng lo < hi cho template tìm chính xác, hoặc lo <= hi cho template lower_bound.

python

# SAI: lo < hi cho tìm chính xác — bỏ sót khi mảng còn 1 phần tử
def binary_search_buggy(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:          # ← khi lo == hi, không kiểm tra phần tử cuối!
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1               # miss khi target ở vị trí cuối cùng

Tại sao sai: Khi lo == hi, vẫn còn 1 phần tử chưa kiểm tra. Với template tìm chính xác (hi = n-1, cập nhật mid ± 1), phải dùng lo <= hi. Với template lower_bound (hi = n, cập nhật hi = mid), dùng lo < hi.

python

# ĐÚNG: lo <= hi cho tìm chính xác
def binary_search_correct(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:          # ← kiểm tra cả khi còn 1 phần tử
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

❌ Sai lầm 3: Cập nhật sai biên — vòng lặp vô hạn

Vấn đề: Trong lower_bound, cập nhật hi = mid - 1 thay vì hi = mid.

python

# SAI: hi = mid - 1 trong lower_bound — bỏ sót đáp án
def lower_bound_buggy(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] >= target:
            hi = mid - 1    # ← nếu arr[mid] == target, bỏ qua chính đáp án!
        else:
            lo = mid + 1
    return lo

Tại sao sai: Khi arr[mid] == target, mid có thể là vị trí trái nhất cần tìm. Cập nhật hi = mid - 1 loại bỏ luôn đáp án. Ngược lại, nếu dùng lo = mid (thay vì mid + 1) trong nhánh else, vòng lặp không bao giờ dừng khi hi - lo == 1.

python

# ĐÚNG: hi = mid (giữ mid trong vùng xét)
def lower_bound_correct(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] >= target:
            hi = mid       # ← mid vẫn có thể là đáp án
        else:
            lo = mid + 1   # ← mid chắc chắn không phải, loại bỏ an toàn
    return lo

❌ Sai lầm 4: Quên kiểm tra mảng đã sorted

Vấn đề: Áp dụng binary search mà không verify precondition.

python

# SAI: binary search trên dữ liệu có thể chưa sort
def find_user(users, target_id):
    # users có thể chưa sort theo id!
    return binary_search(users, target_id)

Tại sao sai: Binary search trên mảng chưa sort cho kết quả sai âm thầm — không error, không exception, chỉ kết quả wrong. Trong production, đây là loại bug nguy hiểm nhất vì khó phát hiện qua testing thông thường.

python

# ĐÚNG: verify hoặc enforce sorted precondition
def find_user(users, target_id):
    assert all(users[i].id <= users[i+1].id for i in range(len(users)-1)), \
        "Binary search requires sorted input"
    return binary_search(users, target_id)

❌ Sai lầm 5: Dùng `(lo + hi) / 2` với floating point

Vấn đề: Dùng lo + (hi - lo) / 2 cho binary search trên số thực.

python

# KHÔNG CẦN THIẾT: overflow không xảy ra với float
mid = lo + (hi - lo) / 2

# ĐƠN GIẢN HƠN và chính xác hơn cho float
mid = (lo + hi) / 2

Tại sao: Floating point không overflow như integer — nó trả về inf. Hơn nữa, (lo + hi) / 2 chính xác hơn lo + (hi - lo) / 2 do ít phép tính hơn → ít precision loss hơn. Trick tránh overflow chỉ áp dụng cho integer.

Under the Hood

Hiệu năng

Metric	Giá trị	Ghi chú
Time (worst)	O(log n)	Chính xác ⌊log₂(n)⌋ + 1 phép so sánh
Time (best)	O(1)	Target ở chính giữa
Time (avg)	O(log n)	~log₂(n) - 1 phép so sánh
Space (iterative)	O(1)	Chỉ vài biến
Space (recursive)	O(log n)	Stack frames

Để trực quan: mảng 1 triệu phần tử cần tối đa 20 phép so sánh. Mảng 1 tỷ phần tử — 30 phép so sánh. Mỗi lần dữ liệu tăng gấp đôi, chỉ thêm đúng 1 bước.

Branch prediction impact

Binary search có pattern truy cập không đoán được — mỗi bước nhảy sang nửa trái hoặc phải tùy thuộc vào dữ liệu. CPU branch predictor đạt accuracy chỉ ~50% (gần như random). Đây là lý do binary search trên mảng nhỏ thua linear search — linear search có branch prediction gần 100%.

Một optimization ít người biết: branchless binary search dùng conditional move thay vì branch, loại bỏ hoàn toàn branch misprediction penalty. GCC/Clang optimize std::lower_bound theo hướng này khi bật -O2.

Binary search trên array vs BST

Cùng O(log n), nhưng binary search trên sorted array nhanh hơn đáng kể so với BST cho dữ liệu tĩnh:

Tiêu chí	Sorted Array + Binary Search	Binary Search Tree
Cache locality	Tốt — dữ liệu liên tiếp	Kém — nodes phân tán heap
Space overhead	0 — chỉ dữ liệu	~2-3x — pointers trái/phải
Insert/Delete	O(n) — phải dịch chuyển	O(log n) — chỉ update pointers
Static data	✅ Tối ưu	❌ Lãng phí
Dynamic data	❌ Quá chậm khi insert	✅ Phù hợp

Quy tắc: dữ liệu tĩnh hoặc ít thay đổi → sorted array. Dữ liệu thường xuyên insert/delete → BST (hoặc balanced BST).

So sánh với Interpolation Search

Interpolation search ước lượng vị trí target dựa trên giá trị, thay vì luôn chia đôi. Với dữ liệu phân bố đều, đạt O(log log n) — nhanh hơn binary search. Nhưng worst case O(n) khi dữ liệu phân bố lệch. Binary search luôn đảm bảo O(log n) bất kể phân bố.

Checklist ghi nhớ

✅ Checklist triển khai

Template cơ bản

[ ] Phân biệt 3 template: tìm chính xác (<=, mid±1), lower_bound (<, hi=mid), upper_bound (<, lo=mid+1)
[ ] Luôn dùng mid = lo + (hi - lo) / 2 thay vì (lo + hi) / 2 cho integer
[ ] Kiểm tra mảng đã sorted trước khi áp dụng binary search

Biến thể nâng cao

[ ] Cài đặt được parametric search: binary search trên không gian đáp án
[ ] Binary search trên số thực: lặp cố định 100 lần hoặc dùng epsilon
[ ] Tìm kiếm trên mảng rotated sorted: xác định nửa nào sorted

Production awareness

[ ] Biết dùng thư viện chuẩn: bisect (Python), std::lower_bound (C++), Arrays.binarySearch (Java), sort.Search (Go)
[ ] Hiểu khi nào binary search thua linear search (n nhỏ, cache effects)
[ ] Recursive binary search: chỉ dùng khi cần — iterative an toàn hơn về stack

Phỏng vấn

[ ] Giải thích được tại sao (lo + hi) / 2 gây overflow
[ ] Viết đúng binary search trong 5 phút mà không debug
[ ] Nhận diện khi nào bài toán giải được bằng "binary search on answer"

Bài tập luyện tập

Bài 1: Tìm phần tử đầu tiên và cuối cùng — Foundation

Đề bài: Cho mảng sorted nums và target, tìm vị trí đầu tiên và cuối cùng của target. Nếu không tìm thấy, trả về [-1, -1]. Yêu cầu O(log n).

Input: nums = [5, 7, 7, 8, 8, 10], target = 8Output: [3, 4]

🧠 Quiz

Tại sao mid = (lo + hi) / 2 nguy hiểm trong Java/C++?

[ ] A. Kết quả luôn sai
[ ] B. Chậm hơn phép trừ
[x] C. lo + hi có thể vượt giới hạn integer, gây integer overflow → mid âm
[ ] D. Chỉ lỗi khi mảng rỗng Giải thích: Khi lo và hi đều lớn (gần INT_MAX/2), tổng vượt INT_MAX. Trong Java/C++, integer overflow wrap around thành số âm → mid âm → crash khi truy cập arr[mid]. Python không có vấn đề này vì integer Python không bị giới hạn kích thước.

💡 Gợi ý

Dùng lower_bound tìm vị trí đầu tiên ≥ target
Dùng upper_bound tìm vị trí đầu tiên > target, trừ 1 = vị trí cuối cùng
Kiểm tra: nếu lower_bound trỏ đến giá trị ≠ target → target không tồn tại

✅ Lời giải

C++PythonJavaGo

cpp

std::vector<int> searchRange(const std::vector<int>& nums, int target) {
    auto lo_it = std::lower_bound(nums.begin(), nums.end(), target);
    if (lo_it == nums.end() || *lo_it != target)
        return {-1, -1};
    auto hi_it = std::upper_bound(lo_it, nums.end(), target);
    return {(int)(lo_it - nums.begin()), (int)(hi_it - nums.begin()) - 1};
}

python

from bisect import bisect_left, bisect_right

def search_range(nums: list[int], target: int) -> list[int]:
    lo = bisect_left(nums, target)
    if lo >= len(nums) or nums[lo] != target:
        return [-1, -1]
    hi = bisect_right(nums, target) - 1
    return [lo, hi]

java

public static int[] searchRange(int[] nums, int target) {
    int lo = lowerBound(nums, target);
    if (lo >= nums.length || nums[lo] != target)
        return new int[]{-1, -1};
    int hi = upperBound(nums, target) - 1;
    return new int[]{lo, hi};
}

func searchRange(nums []int, target int) []int {
    lo := sort.SearchInts(nums, target)
    if lo >= len(nums) || nums[lo] != target {
        return []int{-1, -1}
    }
    hi := sort.SearchInts(nums, target+1) - 1
    return []int{lo, hi}
}

Phân tích: Time O(log n) — hai lần binary search. Space O(1). Đây là LeetCode #34, pattern cực kỳ phổ biến trong phỏng vấn.

Bài 2: Tìm kiếm trong mảng xoay — Intermediate

Đề bài: Mảng sorted bị xoay tại một pivot không biết trước. Tìm target trong O(log n). Không có phần tử trùng lặp.

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0Output: 4

🧠 Quiz

Trong mảng rotated sorted [4, 5, 6, 7, 0, 1, 2], khi lo=0, hi=6, mid=3, nửa nào đang sorted?

[x] A. Nửa trái [4, 5, 6, 7] vì nums[lo]=4 ≤ nums[mid]=7
[ ] B. Nửa phải [0, 1, 2] vì nó chứa các giá trị nhỏ
[ ] C. Cả hai nửa đều sorted
[ ] D. Không nửa nào sorted Giải thích: Kiểm tra nums[lo] <= nums[mid]. Nếu đúng → nửa trái sorted. Trong ví dụ: nums[0]=4 ≤ nums[3]=7 → nửa trái [4,5,6,7] sorted. Nửa phải [0,1,2] cũng sorted nhưng ta chỉ cần xác định một nửa để quyết định hướng tìm.

💡 Gợi ý

Luôn có ít nhất một nửa đang sorted
Kiểm tra nums[lo] <= nums[mid] để biết nửa nào sorted
Nếu target nằm trong range của nửa sorted → tìm ở đó. Ngược lại → tìm nửa kia.

✅ Lời giải

python

def search_rotated(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid

        if nums[lo] <= nums[mid]:
            # Nửa trái sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # Nửa phải sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Phân tích: Time O(log n), Space O(1). LeetCode #33. Cẩn thận với điều kiện <= trong nums[lo] <= target < nums[mid] — thiếu dấu = sẽ bỏ sót khi target == nums[lo].

Bài 3: Chia mảng sao cho max sum nhỏ nhất — Advanced (Parametric Search)

Đề bài: Cho mảng nums và số k, chia mảng thành k nhóm liên tiếp (không được xáo trộn thứ tự) sao cho tổng nhóm lớn nhất là nhỏ nhất có thể. Trả về giá trị tổng nhóm lớn nhất đó.

Input: nums = [7, 2, 5, 10, 8], k = 2Output: 18 (chia thành [7, 2, 5] và [10, 8], max sum = 18)

🧠 Quiz

Parametric search áp dụng được khi nào?

[ ] A. Khi mảng đã sorted
[ ] B. Khi cần tìm phần tử cụ thể
[x] C. Khi hàm kiểm tra có tính monotonic (FFF...TTT) trên không gian đáp án
[ ] D. Chỉ khi dữ liệu là số nguyên Giải thích: Parametric search binary search trên đáp án, không phải trên mảng. Điều kiện duy nhất: hàm canAchieve(x) phải monotonic — nếu x đủ lớn thì True, x quá nhỏ thì False, và không dao động. Trong bài này: max_sum quá nhỏ → không chia được, max_sum đủ lớn → chia được.

💡 Gợi ý

Đáp án nằm trong range [max(nums), sum(nums)]
Binary search trên giá trị max_sum
Viết hàm can_split(nums, k, max_sum): tham lam chia nhóm, nếu ≤ k nhóm → True

✅ Lời giải

python

def split_array(nums: list[int], k: int) -> int:
    def can_split(max_sum: int) -> bool:
        """Có thể chia thành ≤ k nhóm với mỗi nhóm ≤ max_sum?"""
        groups = 1
        current_sum = 0
        for num in nums:
            if current_sum + num > max_sum:
                groups += 1
                current_sum = num
                if groups > k:
                    return False
            else:
                current_sum += num
        return True

    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_split(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Phân tích: Time O(n × log(sum - max)). Space O(1). LeetCode #410 — bài kinh điển về parametric search. Pattern này xuất hiện rất nhiều trong competitive programming và phỏng vấn senior.

Liên kết học tiếp

Từ khóa glossary: Binary Search, lower bound, upper bound, parametric search, bisect, interpolation search, divide and conquer, off-by-one, integer overflow

Tìm kiếm liên quan: tìm kiếm nhị phân, chia đôi, tìm biên trái, tìm biên phải, binary search on answer, search on monotonic function

Binary Search — Tìm kiếm nhị phân ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Tìm giá trị chính xác — Iterative ​

Tìm giá trị chính xác — Recursive ​

Lower Bound — Tìm vị trí trái nhất (≥ target) ​

Upper Bound — Tìm vị trí phải nhất (> target) ​

Parametric Search — Binary search trên đáp án ​

Binary Search trên số thực ​

Thực chiến ​

Tình huống: Tìm phiên bản lỗi đầu tiên (First Bad Version) ​

Tình huống: Tìm kiếm trong mảng sorted đã bị xoay (Rotated Sorted Array) ​

Sai lầm điển hình ​

❌ Sai lầm 1: Integer overflow khi tính mid ​

❌ Sai lầm 2: Nhầm điều kiện vòng lặp — < vs <= ​

❌ Sai lầm 3: Cập nhật sai biên — vòng lặp vô hạn ​

❌ Sai lầm 4: Quên kiểm tra mảng đã sorted ​

❌ Sai lầm 5: Dùng (lo + hi) / 2 với floating point ​

Under the Hood ​

Hiệu năng ​

Branch prediction impact ​

Binary search trên array vs BST ​

So sánh với Interpolation Search ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Tìm phần tử đầu tiên và cuối cùng — Foundation ​

Bài 2: Tìm kiếm trong mảng xoay — Intermediate ​

Bài 3: Chia mảng sao cho max sum nhỏ nhất — Advanced (Parametric Search) ​

Liên kết học tiếp ​

Binary Search — Tìm kiếm nhị phân

Bức tranh tư duy

Cốt lõi kỹ thuật

Tìm giá trị chính xác — Iterative

Tìm giá trị chính xác — Recursive

Lower Bound — Tìm vị trí trái nhất (≥ target)

Upper Bound — Tìm vị trí phải nhất (> target)

Parametric Search — Binary search trên đáp án

Binary Search trên số thực

Thực chiến

Tình huống: Tìm phiên bản lỗi đầu tiên (First Bad Version)

Tình huống: Tìm kiếm trong mảng sorted đã bị xoay (Rotated Sorted Array)

Sai lầm điển hình

❌ Sai lầm 1: Integer overflow khi tính mid

❌ Sai lầm 2: Nhầm điều kiện vòng lặp — `<` vs `<=`

❌ Sai lầm 3: Cập nhật sai biên — vòng lặp vô hạn

❌ Sai lầm 4: Quên kiểm tra mảng đã sorted

❌ Sai lầm 5: Dùng `(lo + hi) / 2` với floating point

Under the Hood

Hiệu năng

Branch prediction impact

Binary search trên array vs BST

So sánh với Interpolation Search

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Tìm phần tử đầu tiên và cuối cùng — Foundation

Bài 2: Tìm kiếm trong mảng xoay — Intermediate

Bài 3: Chia mảng sao cho max sum nhỏ nhất — Advanced (Parametric Search)

Liên kết học tiếp