Tìm kiếm — Linear Search & Binary Search

Năm 2006, Joshua Bloch — tác giả của Java Collections Framework — phát hiện bug trong chính implementation của binary search trong JDK đã tồn tại 9 năm: (lo + hi) / 2 bị integer overflow. Nếu một kỹ sư cấp senior tại Google còn mắc lỗi này, bạn cần hiểu tại sao nó xảy ra và cách phòng tránh.

🎯 Mục tiêu

🎯 Sau bài học này, bạn sẽ:

Biết khi nào Linear Search là lựa chọn đúng
Viết Binary Search không bug (overflow-safe mid)
Thành thạo lower_bound, upper_bound, search-on-answer
Nhận diện vấn đề có thể giải bằng Binary Search
Tránh 4 sai lầm kinh điển mà ai cũng từng mắc

1. Linear Search — Khi đơn giản là đủ

Trước khi lao vào Binary Search, hãy hiểu rõ khi nào Linear Search mới là lựa chọn đúng đắn.

Khi nào dùng Linear Search?

Tình huống	Lý do
Dữ liệu chưa sắp xếp	Không có lựa chọn nào khác
Mảng nhỏ (n < 100)	Overhead của Binary Search không đáng
Tìm first/last không theo thứ tự	Không tận dụng được tính sorted
Dữ liệu dạng stream	Không có random access

Implementation cơ bản

C++JavaPython

cpp

int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < (int)arr.size(); i++)
        if (arr[i] == target) return i;
    return -1;
}

java

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++)
        if (arr[i] == target) return i;
    return -1;
}

python

def linear_search(arr: list[int], target: int) -> int:
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Sentinel Trick — Tối ưu nhỏ nhưng hay

Ý tưởng: thêm target vào cuối mảng → bỏ kiểm tra bounds trong loop → tiết kiệm 1 phép so sánh mỗi iteration.

python

def linear_search_sentinel(arr: list[int], target: int) -> int:
    n = len(arr)
    if n == 0:
        return -1
    last = arr[n - 1]
    arr[n - 1] = target      # Sentinel
    i = 0
    while arr[i] != target:
        i += 1
    arr[n - 1] = last        # Restore
    if i < n - 1 or arr[n - 1] == target:
        return i
    return -1

Complexity: O(n) time, O(1) space. Không cách nào nhanh hơn cho unsorted data.

📌 Sentinel trick — dùng ở đâu?

Competitive programming: có, tiết kiệm constant factor. Production code: hiếm khi, vì nó mutate input array. Biết trick này cho phỏng vấn, nhưng production nên dùng phiên bản cơ bản.

2. Binary Search — Nghệ thuật chia đôi

Binary Search giảm search space đi một nửa sau mỗi bước. Từ 1 triệu phần tử → chỉ cần ~20 phép so sánh. Nhưng implement đúng thì không hề đơn giản.

2.1 The Classic Bug — Integer Overflow

int mid = (lo + hi) / 2;  // ❌ BUG: lo + hi có thể overflow

Tại sao lại bug? Nếu lo = 2,000,000,000 và hi = 2,000,000,000, thì lo + hi = 4,000,000,000 > INT_MAX (2,147,483,647) → overflow → mid âm → crash. Bug này tồn tại trong JDK từ 1997 đến 2006 — gần một thập kỷ!

3 cách tính mid an toàn:

C++JavaPython

cpp

// Cách 1: Công thức an toàn — dùng mọi nơi
int mid = lo + (hi - lo) / 2;

// Cách 2: Bit shift (tương đương, nhanh hơn 1 CPU cycle)
int mid = lo + ((hi - lo) >> 1);

java

// Cách 1: Công thức an toàn
int mid = lo + (hi - lo) / 2;

// Cách 2: Unsigned right shift — Java-specific
int mid = (lo + hi) >>> 1;
// >>> shift bit sang phải và ĐIỀN 0 vào bit cao nhất
// → luôn cho kết quả dương, kể cả khi lo + hi overflow

python

# Python KHÔNG bị integer overflow (arbitrary-precision integers)
mid = (lo + hi) // 2          # ✅ An toàn trong Python
mid = lo + (hi - lo) // 2     # ✅ Cũng đúng, consistent với C++/Java

# NHƯNG: bạn PHẢI hiểu vấn đề overflow cho C++/Java phỏng vấn!

⚠️ Quy tắc vàng

Luôn dùng lo + (hi - lo) / 2 thay vì (lo + hi) / 2. Đây không chỉ là best practice — mà là yêu cầu bắt buộc trong mọi cuộc phỏng vấn. Interviewer sẽ đánh giá thấp nếu bạn dùng cách không safe.

2.2 Standard Binary Search — Template chuẩn

C++JavaPython

cpp

int binarySearch(const vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;
    while (lo <= hi) {                    // Inclusive bounds: [lo, hi]
        int mid = lo + (hi - lo) / 2;    // Overflow-safe
        if (arr[mid] == target) return mid;
        else if (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;
}

python

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

VISUALIZER STATES — Binary Search:
State 1: RANGE → highlight [lo..hi] in blue
State 2: MID_CALC → mid pointer in yellow
State 3: COMPARE → arr[mid] vs target (<, >, =)
State 4: ELIMINATE → half grays out
State 5: FOUND → green (or NOT_FOUND: all gray)

2.3 ASCII Trace — Chạy tay để hiểu

Mảng: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] — tìm 23:

Step 1: lo=0, hi=9, mid=4 → arr[4]=16 < 23  → lo=5
Step 2: lo=5, hi=9, mid=7 → arr[7]=56 > 23  → hi=6
Step 3: lo=5, hi=6, mid=5 → arr[5]=23 = 23  → FOUND at index 5 ✅

Search space: 10 → 5 → 2 → 1  (3 bước = ⌊log₂(10)⌋)

💡 Mẹo trace

Khi trace binary search, chỉ cần viết lo, hi, mid mỗi bước. Đừng viết lại toàn bộ mảng.

3. Binary Search Variations — Interview Gold

Standard binary search hiếm khi hỏi trực tiếp — interviewer muốn xem bạn xử lý các biến thể.

3.1 lower_bound — Vị trí đầu tiên ≥ target

Bài toán: tìm index nhỏ nhất i sao cho arr[i] >= target. Nếu không có phần tử nào ≥ target, trả về len(arr).

Khác biệt so với standard binary search: hi = len(arr) (không phải len(arr)-1), while lo < hi (không phải <=), hi = mid (không phải mid-1).

C++Python

cpp

int lowerBound(const vector<int>& arr, int target) {
    int lo = 0, hi = arr.size();    // hi = size(), không phải size()-1
    while (lo < hi) {               // <, không phải <=
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid;              // mid, không phải mid-1
    }
    return lo;
}

python

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

Ví dụ: arr = [1, 3, 3, 5, 7], target = 3 → lower_bound trả về 1 (index đầu tiên có giá trị ≥ 3).

3.2 upper_bound — Vị trí đầu tiên > target

Bài toán: tìm index nhỏ nhất i sao cho arr[i] > target. Template gần giống lower_bound — chỉ khác dấu <=:

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:     # Chỉ khác lower_bound ở dấu <=
            lo = mid + 1
        else:
            hi = mid
    return lo

C++/Java: tương tự, chỉ đổi < thành <= trong điều kiện so sánh.

Ví dụ: arr = [1, 3, 3, 5, 7], target = 3 → upper_bound trả về 3 (index đầu tiên có giá trị > 3).

📌 Ứng dụng kết hợp lower_bound + upper_bound

Đếm số lần xuất hiện: count = upper_bound(target) - lower_bound(target)
Kiểm tra tồn tại: lower_bound(target) < len(arr) and arr[lower_bound(target)] == target
Tìm range: tất cả phần tử = target nằm trong [lower_bound, upper_bound)

3.3 Search-on-Answer Pattern

Pattern mạnh nhất của Binary Search. Thay vì search trên mảng, ta search trên đáp án: nếu k thỏa điều kiện thì k+1 cũng thỏa (monotonic).

Template:

python

def search_on_answer(lo: int, hi: int, is_feasible) -> int:
    """Tìm giá trị nhỏ nhất trong [lo, hi] thỏa mãn is_feasible."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            hi = mid            # mid thỏa → tìm nhỏ hơn
        else:
            lo = mid + 1        # mid không thỏa → tăng lên
    return lo

Các bài kinh điển dùng search-on-answer:

Bài toán	is_feasible(mid) kiểm tra gì?
Koko Eating Bananas	Ăn với tốc độ `mid` → xong trong ≤ H giờ?
Ship Packages in D Days	Capacity = `mid` → ship hết trong ≤ D ngày?
Split Array Largest Sum	Max sum = `mid` → chia được thành ≤ m phần?
Minimum Time to Finish	Thời gian `mid` → hoàn thành tất cả task?

💡 Ví dụ: Koko Eating Bananas (LeetCode #875)

python

def minEatingSpeed(piles: list[int], h: int) -> int:
    def is_feasible(speed):
        return sum((p + speed - 1) // speed for p in piles) <= h
    return search_on_answer(1, max(piles), is_feasible)

Thay vì thử mọi speed O(n × max), binary search chỉ cần O(n × log(max)).

4. Real-world Binary Search

Binary Search xuất hiện khắp nơi trong software engineering:

Ứng dụng	Cách dùng
`git bisect`	Binary search trên commit history để tìm commit gây bug
Package managers (npm, pip)	Tìm phiên bản compatible trong range
Database B-Tree index	Binary search trong mỗi node để tìm key
Load testing	Search-on-answer tìm max RPS trước khi hệ thống sập

💡 git bisect — công cụ anh em nên biết

bash

git bisect start
git bisect bad                  # Commit hiện tại có bug
git bisect good abc1234         # Commit này chưa có bug
# Git checkout commit giữa → test → đánh dấu good/bad → lặp lại
# 1000 commits → chỉ cần ~10 bước!

5. ⚡ Operational Complexity

n	Linear O(n)	Binary O(log n)	Tỉ lệ
1,000	1,000 ops	~10 ops	100×
1,000,000	~1ms	~20 ops (~0.00002ms)	50,000×
10⁹	~1 giây	~30 ops	33,000,000×
10¹⁸	Không khả thi	~60 ops (!)	♾️

⚠️ Điều kiện tiên quyết

Binary Search chỉ hoạt động trên dữ liệu ĐÃ SẮP XẾP. Với single query trên unsorted data: sort O(n log n) + search O(log n) = O(n log n) — Linear Search O(n) nhanh hơn! Binary Search chỉ lợi khi có nhiều queries trên cùng mảng.

6. Sai lầm điển hình — Đừng mắc lại

❌ Lỗi 1: Integer overflow khi tính mid

cpp

int mid = (lo + hi) / 2;          // ❌ overflow khi lo + hi > INT_MAX
int mid = lo + (hi - lo) / 2;     // ✅ Luôn dùng cách này

❌ Lỗi 2: Sai loop condition với inclusive bounds

cpp

while (lo < hi) { ... hi = mid - 1; }   // ❌ Bỏ sót element khi lo == hi
while (lo <= hi) { ... hi = mid - 1; }  // ✅ Đúng với inclusive [lo, hi]

❌ Lỗi 3: Infinite loop — `hi = mid` với `while (lo <= hi)`

cpp

while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;       // ❌ Khi lo == hi == mid → loop forever!
}
// ✅ Với while (lo <= hi), PHẢI dùng hi = mid - 1

❌ Lỗi 4: Binary search trên unsorted array

Binary Search giả định mảng sorted. Nếu không sorted → kết quả sai hoàn toàn, không báo lỗi.

❌ Lỗi 5: Nhầm template lower_bound / upper_bound

python

# lower_bound: arr[mid] < target  → lo = mid + 1 | else hi = mid
# upper_bound: arr[mid] <= target → lo = mid + 1 | else hi = mid
#                          ^^ chỉ khác DUY NHẤT dấu <=

🚫 Cách nhớ để không nhầm

lower_bound dùng < → tìm phần tử đầu tiên ≥ target
upper_bound dùng <= → tìm phần tử đầu tiên > target
Cả hai: while lo < hi + hi = mid (không phải mid - 1)

7. Bài tập thực hành

🧠 Quiz

Câu 1: Khi nào Linear Search tốt hơn Binary Search?

[x] A. Mảng chưa sắp xếp và chỉ cần tìm một lần
[ ] B. Mảng đã sắp xếp và cần tìm nhiều lần
[ ] C. Mảng lớn (n > 10⁶) đã sắp xếp
[ ] D. Không bao giờ — Binary Search luôn tốt hơn

Giải thích: Mảng chưa sorted + tìm 1 lần: sort O(n log n) + search O(log n) > linear O(n).

🧠 Quiz

Câu 2: [1, 3, 3, 3, 5, 7], target = 3 → lower_bound trả về?

[ ] A. 0
[x] B. 1
[ ] C. 3
[ ] D. -1

Giải thích: lower_bound tìm index đầu tiên ≥ target. arr[1] = 3 là phần tử đầu tiên ≥ 3. upper_bound sẽ trả về 4.

🧠 Quiz

Câu 3: Dòng nào tính mid AN TOÀN?

[ ] A. int mid = (lo + hi) / 2;
[x] B. int mid = lo + (hi - lo) / 2;
[ ] C. int mid = (lo + hi) >> 1;
[x] D. int mid = (lo + hi) >>> 1; (Java only)

Giải thích: A, C bị overflow khi lo + hi > INT_MAX. B an toàn vì hi - lo không overflow. D an toàn nhờ unsigned right shift.

🐛 Spot the Bug

python

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        elif arr[mid] > target:
            hi = mid          # 🐛 Bug ở đây!
        else:
            return mid
    return -1

✅ Đáp án

Bug: hi = mid với while lo <= hi gây infinite loop. Khi lo == hi == mid và arr[mid] > target: hi = mid không thay đổi → loop mãi.

Fix: hi = mid - 1. Nguyên tắc: while lo <= hi ↔ hi = mid - 1. while lo < hi ↔ hi = mid. Không mix!

🧩 Parsons Problem

Sắp xếp thành hàm `lower_bound` đúng

Kéo thả các dòng code vào đúng thứ tự:

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

✅ Đáp án

python

def lower_bound(arr, target):       # 1
    lo, hi = 0, len(arr)            # 2 — hi = len(arr), KHÔNG phải len(arr)-1
    while lo < hi:                  # 3 — <, KHÔNG phải <=
        mid = lo + (hi - lo) // 2   # 4
        if arr[mid] < target:       # 5
            lo = mid + 1            # 6
        else:                       # 7
            hi = mid                # 8 — mid, KHÔNG phải mid-1
    return lo                       # 9

8. Tổng kết

✅ Checklist triển khai

Linear Search

[ ] Hiểu khi nào Linear Search là lựa chọn đúng (unsorted, small n, stream)
[ ] Biết Sentinel trick và trade-off của nó

Binary Search — Cơ bản

[ ] Luôn dùng lo + (hi - lo) / 2 — không bao giờ (lo + hi) / 2
[ ] Phân biệt inclusive (lo <= hi, hi = mid-1) vs half-open (lo < hi, hi = mid)
[ ] Trace được binary search trên giấy trong < 2 phút

Binary Search — Variations

[ ] Implement lower_bound / upper_bound không cần nhìn template
[ ] Áp dụng search-on-answer pattern cho bài toán tối ưu
[ ] Không mix loop condition với bound update

📍 Trang tiếp theo

Bạn đã master searching — công cụ O(log n) mạnh nhất trong toolkit. Tiếp theo, xây dựng nền tảng data structures:

→ Linear Data Structures — Array, Linked List, Stack, Queue

Từ khóa tìm kiếm: binary search, linear search, tìm kiếm nhị phân, tìm kiếm tuyến tính, overflow-safe mid, lower_bound, upper_bound, search on answer, parametric search, git bisect, sentinel search

Tìm kiếm — Linear Search & Binary Search ​

1. Linear Search — Khi đơn giản là đủ ​

Khi nào dùng Linear Search? ​

Implementation cơ bản ​

Sentinel Trick — Tối ưu nhỏ nhưng hay ​

2. Binary Search — Nghệ thuật chia đôi ​

2.1 The Classic Bug — Integer Overflow ​

2.2 Standard Binary Search — Template chuẩn ​

2.3 ASCII Trace — Chạy tay để hiểu ​

3. Binary Search Variations — Interview Gold ​

3.1 lower_bound — Vị trí đầu tiên ≥ target ​

3.2 upper_bound — Vị trí đầu tiên > target ​

3.3 Search-on-Answer Pattern ​

4. Real-world Binary Search ​

5. ⚡ Operational Complexity ​

6. Sai lầm điển hình — Đừng mắc lại ​

❌ Lỗi 1: Integer overflow khi tính mid ​

❌ Lỗi 2: Sai loop condition với inclusive bounds ​

❌ Lỗi 3: Infinite loop — hi = mid với while (lo <= hi) ​

❌ Lỗi 4: Binary search trên unsorted array ​

❌ Lỗi 5: Nhầm template lower_bound / upper_bound ​

7. Bài tập thực hành ​

🧠 Quiz ​

🐛 Spot the Bug ​

🧩 Parsons Problem ​

Sắp xếp thành hàm lower_bound đúng ​

8. Tổng kết ​

📍 Trang tiếp theo ​

Tìm kiếm — Linear Search & Binary Search

1. Linear Search — Khi đơn giản là đủ

Khi nào dùng Linear Search?

Implementation cơ bản

Sentinel Trick — Tối ưu nhỏ nhưng hay

2. Binary Search — Nghệ thuật chia đôi

2.1 The Classic Bug — Integer Overflow

2.2 Standard Binary Search — Template chuẩn

2.3 ASCII Trace — Chạy tay để hiểu

3. Binary Search Variations — Interview Gold

3.1 lower_bound — Vị trí đầu tiên ≥ target

3.2 upper_bound — Vị trí đầu tiên > target

3.3 Search-on-Answer Pattern

4. Real-world Binary Search

5. ⚡ Operational Complexity

6. Sai lầm điển hình — Đừng mắc lại

❌ Lỗi 1: Integer overflow khi tính mid

❌ Lỗi 2: Sai loop condition với inclusive bounds

❌ Lỗi 3: Infinite loop — `hi = mid` với `while (lo <= hi)`

❌ Lỗi 4: Binary search trên unsorted array

❌ Lỗi 5: Nhầm template lower_bound / upper_bound

7. Bài tập thực hành

🧠 Quiz

🐛 Spot the Bug

🧩 Parsons Problem

Sắp xếp thành hàm `lower_bound` đúng

8. Tổng kết

📍 Trang tiếp theo