Bài học

Tìm kiếm nhị phân trên mảng — các biến thể

Mục tiêu bài học

Sau bài này, em cài đặt đúng hai biến thể lower_bound và upper_bound của tìm kiếm nhị phân, áp dụng được nhị phân lên một mảng đã bị xoay, và tự kiểm tra bằng bất biến vòng lặp $lo \le hi$ để không còn mắc lỗi lệch một đơn vị — lỗi phổ biến nhất khi mới học nhóm kỹ thuật này.

Sau bài này, em cài đặt đúng hai biến thể `lower_bound` và `upper_bound` của tìm kiếm nhị phân, áp dụng được nhị phân lên một mảng đã bị xoay, và tự kiểm tra bằng bất biến vòng lặp $lo \le hi$ để không còn mắc lỗi lệch một đơn vị — lỗi phổ biến nhất khi mới học nhóm kỹ thuật này.

Cần nhớ trước

Em cần vững tìm kiếm nhị phân cơ bản của Tin 10: mảng đã sắp xếp, mỗi bước so sánh $a[mid]$ với $x$ rồi thu hẹp một nửa miền tìm kiếm, độ phức tạp $O(\log n)$ . Bài này không dạy lại phần đó — nó mở rộng phần đó theo hai hướng khác nhau.

Em cần vững tìm kiếm nhị phân cơ bản của Tin 10: mảng đã sắp xếp, mỗi bước so sánh $a[mid]$ với $x$ rồi thu hẹp một nửa miền tìm kiếm, độ phức tạp $O(\log n)$. Bài này không dạy lại phần đó — nó mở rộng phần đó theo hai hướng khác nhau.

So với mức chuẩn: nhị phân ở Tin 10 chỉ trả lời một câu: $x$ có nằm trong mảng hay không, và nếu có thì ở đâu. Đề HSG hỏi khó hơn — mảng có phần tử trùng nhau, và ta cần biết chính xác vị trí đầu tiên hoặc cuối cùng của $x$ , hoặc đếm xem có bao nhiêu phần tử nhỏ hơn hay không lớn hơn một ngưỡng cho trước. Nhị phân kiểu "tìm thấy hay không" không trả lời được câu hỏi dạng đó.

**So với mức chuẩn:** nhị phân ở Tin 10 chỉ trả lời một câu: $x$ có nằm trong mảng hay không, và nếu có thì ở đâu. Đề HSG hỏi khó hơn — mảng có phần tử trùng nhau, và ta cần biết chính xác vị trí *đầu tiên* hoặc *cuối cùng* của $x$, hoặc đếm xem có bao nhiêu phần tử nhỏ hơn hay không lớn hơn một ngưỡng cho trước. Nhị phân kiểu "tìm thấy hay không" không trả lời được câu hỏi dạng đó.

Bài toán mở đầu

Một lớp có học sinh với điểm kiểm tra được lưu trong mảng đã sắp xếp tăng dần, và có nhiều bạn trùng điểm — ví dụ mảng điểm $[1, 3, 3, 5, 5, 5, 8, 10]$ . Cô giáo hỏi: có bao nhiêu bạn đạt từ 5 điểm trở xuống? Nếu chỉ biết nhị phân kiểu Tin 10, em tìm được MỘT vị trí có giá trị bằng 5 (nếu có) — nhưng không biết có bao nhiêu bạn đứng trước hay sau vị trí đó cũng bằng 5. Cần một dạng nhị phân khác: nhị phân tìm biên, không phải nhị phân tìm một giá trị.

Một lớp có học sinh với điểm kiểm tra được lưu trong mảng đã sắp xếp tăng dần, và có nhiều bạn trùng điểm — ví dụ mảng điểm $[1, 3, 3, 5, 5, 5, 8, 10]$. Cô giáo hỏi: có bao nhiêu bạn đạt từ 5 điểm trở xuống? Nếu chỉ biết nhị phân kiểu Tin 10, em tìm được MỘT vị trí có giá trị bằng 5 (nếu có) — nhưng không biết có bao nhiêu bạn đứng trước hay sau vị trí đó cũng bằng 5. Cần một dạng nhị phân khác: nhị phân tìm *biên*, không phải nhị phân tìm *một giá trị*.

Ý tưởng cốt lõi — lower_bound và upper_bound

Mở rộng dành cho HSG

lower_bound và upper_bound không nằm trong nội dung chuẩn Tin 11 — đây là hai hàm nền tảng của lập trình thi đấu, dùng lại xuyên suốt các bài sau của khóa này.

lower_bound(x) là vị trí đầu tiên trong mảng mà giá trị tại đó $\ge x$ — nói cách khác, vị trí nhỏ nhất có thể chèn $x$ vào để mảng vẫn giữ thứ tự tăng dần, tính từ bên trái. upper_bound(x) là vị trí đầu tiên mà giá trị tại đó $> x$ . Hai định nghĩa chỉ khác nhau ở dấu so sánh — nhưng từ đó suy ra ngay hai công thức dùng lại rất nhiều: số phần tử bằng đúng $x$ là upper_bound(x) - lower_bound(x), và số phần tử $\le x$ chính là upper_bound(x).

**`lower_bound(x)`** là vị trí đầu tiên trong mảng mà giá trị tại đó $\ge x$ — nói cách khác, vị trí nhỏ nhất có thể chèn $x$ vào để mảng vẫn giữ thứ tự tăng dần, tính từ bên trái. **`upper_bound(x)`** là vị trí đầu tiên mà giá trị tại đó $> x$. Hai định nghĩa chỉ khác nhau ở dấu so sánh — nhưng từ đó suy ra ngay hai công thức dùng lại rất nhiều: số phần tử bằng đúng $x$ là `upper_bound(x) - lower_bound(x)`, và số phần tử $\le x$ chính là `upper_bound(x)`.

Vì sao ý tưởng này tự nhiên: nhị phân Tin 10 hỏi " $a[mid]$ có bằng $x$ không", còn lower_bound/upper_bound hỏi " $a[mid]$ có thỏa một bất đẳng thức hay không" thay vì một phép so sánh bằng. Vì mảng đã sắp xếp, giá trị đúng/sai của bất đẳng thức đó đổi từ sai sang đúng đúng một lần khi quét qua mảng — đúng dạng bài toán nhị phân giải quyết được, dù không còn tìm "giá trị bằng $x$ " nữa. Đây cũng chính là ý sẽ lặp lại ở Bài 2, khi nhị phân không còn chạy trên chỉ số mảng mà chạy trên tập giá trị đáp án.

Vì sao ý tưởng này tự nhiên: nhị phân Tin 10 hỏi "$a[mid]$ có bằng $x$ không", còn `lower_bound`/`upper_bound` hỏi "$a[mid]$ có thỏa một bất đẳng thức hay không" thay vì một phép so sánh bằng. Vì mảng đã sắp xếp, giá trị đúng/sai của bất đẳng thức đó đổi từ sai sang đúng đúng một lần khi quét qua mảng — đúng dạng bài toán nhị phân giải quyết được, dù không còn tìm "giá trị bằng $x$" nữa. Đây cũng chính là ý sẽ lặp lại ở Bài 2, khi nhị phân không còn chạy trên chỉ số mảng mà chạy trên tập giá trị đáp án.

Ví dụ

Ví dụ 1 — Cài đặt lower_bound / upper_bound và đếm phần tử trong một đoạn

1
Nhị phân chuẩn của Tin 10 chỉ trả lời có/không. Ở đây mảng có phần tử trùng lặp và đề hỏi một con số đếm được — không có công thức đóng nào ngoài việc định vị đúng biên trái/biên phải của vùng giá trị cần đếm.
2
```
def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo  # vi tri dau tien co a[i] >= x


def upper_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo  # vi tri dau tien co a[i] > x
```
```python def lower_bound(a, x): lo, hi = 0, len(a) while lo < hi: mid = (lo + hi) // 2 if a[mid] < x: lo = mid + 1 else: hi = mid return lo # vi tri dau tien co a[i] >= x def upper_bound(a, x): lo, hi = 0, len(a) while lo < hi: mid = (lo + hi) // 2 if a[mid] <= x: lo = mid + 1 else: hi = mid return lo # vi tri dau tien co a[i] > x ```
3
Với a = [1, 3, 3, 5, 5, 5, 8, 10] và x = 5, lower_bound chạy qua đúng 3 bước:

Bước 1: lo=0, hi=8, mid=4 → a[mid]=5; a[mid] < 5 là False → hi=4 Bước 2: lo=0, hi=4, mid=2 → a[mid]=3; a[mid] < 5 là True → lo=3 Bước 3: lo=3, hi=4, mid=3 → a[mid]=5; a[mid] < 5 là False → hi=3

Dừng khi $lo = hi = 3$ — lower_bound(a, 5) = 3.
Với `a = [1, 3, 3, 5, 5, 5, 8, 10]` và `x = 5`, `lower_bound` chạy qua đúng 3 bước: Bước 1: lo=0, hi=8, mid=4 → a[mid]=5; a[mid] < 5 là False → hi=4 Bước 2: lo=0, hi=4, mid=2 → a[mid]=3; a[mid] < 5 là True → lo=3 Bước 3: lo=3, hi=4, mid=3 → a[mid]=5; a[mid] < 5 là False → hi=3 Dừng khi $lo = hi = 3$ — `lower_bound(a, 5) = 3`.
4
Số phần tử $\le 5$ trong mảng chính là upper_bound(a, 5). Chạy hàm cho ra 6 — khớp đúng với đếm tay: $\{1, 3, 3, 5, 5, 5\}$ có 6 phần tử. Vậy có 6 bạn đạt từ 5 điểm trở xuống.
Số phần tử $\le 5$ trong mảng chính là `upper_bound(a, 5)`. Chạy hàm cho ra `6` — khớp đúng với đếm tay: $\{1, 3, 3, 5, 5, 5\}$ có 6 phần tử. Vậy có 6 bạn đạt từ 5 điểm trở xuống.
5
Số phần tử bằng đúng 5 là upper_bound(a,5) - lower_bound(a,5) = 6 - 3 = 3 — khớp đúng ba số 5 có trong mảng. Vậy phép tính nhất quán ở cả hai chiều kiểm tra.

Bước cuối: lo = hi = 3 — con trỏ hội tụ đúng tại vị trí đầu tiên có giá trị ≥ 5.

Ví dụ

Ví dụ 2 — Tìm phần tử nhỏ nhất trong mảng xoay (không trùng lặp)

1
Mảng không còn đơn điệu toàn cục — nó bị "xoay" tại một điểm gãy chưa biết. Nhị phân so sánh $a[mid]$ với một giá trị $x$ không còn ý nghĩa, vì ta không tìm $x$ mà tìm chính điểm gãy đó.
Mảng không còn đơn điệu toàn cục — nó bị "xoay" tại một điểm gãy chưa biết. Nhị phân so sánh $a[mid]$ với một giá trị $x$ không còn ý nghĩa, vì ta không tìm $x$ mà tìm chính điểm gãy đó.
2
So sánh $a[mid]$ với $a[hi]$ thay vì với $x$ : nếu $a[mid] > a[hi]$ thì đoạn $lo..mid$ vẫn còn "cao" hơn đầu cuối — điểm gãy (và do đó phần tử nhỏ nhất) nằm bên phải $mid$ . Ngược lại, đoạn $mid..hi$ đã đơn điệu tăng — phần tử nhỏ nhất nằm trong $lo..mid$ , kể cả chính $mid$ .
So sánh $a[mid]$ với $a[hi]$ thay vì với $x$: nếu $a[mid] > a[hi]$ thì đoạn $lo..mid$ vẫn còn "cao" hơn đầu cuối — điểm gãy (và do đó phần tử nhỏ nhất) nằm bên phải $mid$. Ngược lại, đoạn $mid..hi$ đã đơn điệu tăng — phần tử nhỏ nhất nằm trong $lo..mid$, kể cả chính $mid$.

def find_min_rotated(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            # nua trai lo..mid van con "cao" hon a[hi] -> diem gay nam ben phai
            lo = mid + 1
        else:
            # a[mid] <= a[hi] -> doan mid..hi da don dieu -> diem gay o ben trai (ke ca mid)
            hi = mid
    return a[lo]

4
Với a = [8, 12, 16, 1, 4, 6]:

Bước 1: lo=0, hi=5, mid=2 → a[mid]=16, a[hi]=6; a[mid] > a[hi] là True → lo=3 Bước 2: lo=3, hi=5, mid=4 → a[mid]=4, a[hi]=6; a[mid] > a[hi] là False → hi=4 Bước 3: lo=3, hi=4, mid=3 → a[mid]=1, a[hi]=4; a[mid] > a[hi] là False → hi=3

Dừng khi $lo = hi = 3$ — phần tử nhỏ nhất là a[3] = 1.
Với `a = [8, 12, 16, 1, 4, 6]`: Bước 1: lo=0, hi=5, mid=2 → a[mid]=16, a[hi]=6; a[mid] > a[hi] là True → lo=3 Bước 2: lo=3, hi=5, mid=4 → a[mid]=4, a[hi]=6; a[mid] > a[hi] là False → hi=4 Bước 3: lo=3, hi=4, mid=3 → a[mid]=1, a[hi]=4; a[mid] > a[hi] là False → hi=3 Dừng khi $lo = hi = 3$ — phần tử nhỏ nhất là `a[3] = 1`.
5
Mảng gốc trước khi xoay là phần đơn điệu bắt đầu từ giá trị nhỏ nhất — dò bằng mắt trên [8, 12, 16, 1, 4, 6] cũng thấy 1 là số nhỏ nhất. Với mảng [15, 18, 2, 3, 6, 9, 12] cùng thuật toán cho find_min_rotated([15, 18, 2, 3, 6, 9, 12]) = 2, cũng khớp.
Mảng gốc trước khi xoay là phần đơn điệu bắt đầu từ giá trị nhỏ nhất — dò bằng mắt trên `[8, 12, 16, 1, 4, 6]` cũng thấy 1 là số nhỏ nhất. Với mảng `[15, 18, 2, 3, 6, 9, 12]` cùng thuật toán cho `find_min_rotated([15, 18, 2, 3, 6, 9, 12]) = 2`, cũng khớp.

Vì sao vòng lặp luôn dừng đúng — và bẫy khi mảng có phần tử trùng

Cả hai thuật toán trên đều giữ một bất biến: đáp án đúng luôn nằm trong đoạn $[lo, hi]$ (hoặc $[lo, hi)$ với lower_bound/upper_bound), và mỗi bước $mid$ luôn nằm chặt trong đoạn đó nên $hi - lo$ giảm nghiêm ngặt. Đoạn không bao giờ rỗng và luôn thu hẹp — đó là lý do vòng lặp chắc chắn dừng, và dừng sau $O(\log n)$ bước.

Cả hai thuật toán trên đều giữ một **bất biến**: đáp án đúng luôn nằm trong đoạn $[lo, hi]$ (hoặc $[lo, hi)$ với `lower_bound`/`upper_bound`), và mỗi bước $mid$ luôn nằm chặt trong đoạn đó nên $hi - lo$ giảm nghiêm ngặt. Đoạn không bao giờ rỗng và luôn thu hẹp — đó là lý do vòng lặp chắc chắn dừng, và dừng sau $O(\log n)$ bước.

Bẫy thường gặp

Bẫy 1: nhầm dấu < và <= trong điều kiện — đúng một chỗ này quyết định lower_bound hay upper_bound, chép nhầm dấu là sai toàn bộ chứ không phải lệch nhẹ.

Bẫy 2: quên rằng lower_bound/upper_bound khởi tạo hi = len(a) (không phải len(a) - 1) — hi ở đây là biên KHÔNG nằm trong đoạn tìm kiếm, đại diện cho "chèn ở cuối mảng", khác hẳn kiểu hi = len(a) - 1 quen thuộc của nhị phân "có/không".

Bẫy 3: dùng công thức a[mid] > a[hi] trên mảng xoay CÓ phần tử trùng nhau. Khi $a[mid] = a[hi]$ , không thể biết điểm gãy nằm bên nào — cách sửa an toàn là giảm hi đi 1 khi gặp trường hợp bằng, nhưng khi đó độ phức tạp xấu nhất tụt xuống $O(n)$ (ví dụ mảng gần như toàn số giống nhau, chỉ một phần tử khác biệt).

Bẫy 1: nhầm dấu `<` và `<=` trong điều kiện — đúng một chỗ này quyết định `lower_bound` hay `upper_bound`, chép nhầm dấu là sai toàn bộ chứ không phải lệch nhẹ. Bẫy 2: quên rằng `lower_bound`/`upper_bound` khởi tạo `hi = len(a)` (không phải `len(a) - 1`) — `hi` ở đây là biên KHÔNG nằm trong đoạn tìm kiếm, đại diện cho "chèn ở cuối mảng", khác hẳn kiểu `hi = len(a) - 1` quen thuộc của nhị phân "có/không". Bẫy 3: dùng công thức `a[mid] > a[hi]` trên mảng xoay CÓ phần tử trùng nhau. Khi $a[mid] = a[hi]$, không thể biết điểm gãy nằm bên nào — cách sửa an toàn là giảm `hi` đi 1 khi gặp trường hợp bằng, nhưng khi đó độ phức tạp xấu nhất tụt xuống $O(n)$ (ví dụ mảng gần như toàn số giống nhau, chỉ một phần tử khác biệt).

Tóm lại: ba biến thể vừa học — lower_bound, upper_bound, tìm kiếm trên mảng xoay — đều dùng chung một khung: giữ một bất biến đúng trên $[lo, hi]$ , thu hẹp bất biến đó đúng một nửa mỗi bước, dừng khi $lo = hi$ . Khung này áp dụng được cho bất kỳ điều kiện đơn điệu nào, không chỉ so sánh trực tiếp giá trị trong mảng.

**Tóm lại:** ba biến thể vừa học — `lower_bound`, `upper_bound`, tìm kiếm trên mảng xoay — đều dùng chung một khung: giữ một bất biến đúng trên $[lo, hi]$, thu hẹp bất biến đó đúng một nửa mỗi bước, dừng khi $lo = hi$. Khung này áp dụng được cho bất kỳ điều kiện đơn điệu nào, không chỉ so sánh trực tiếp giá trị trong mảng.

Bước tiếp theo là bước nhảy quan trọng nhất của cả khóa: thay vì nhị phân trên CHỈ SỐ của một mảng, ta nhị phân trên TẬP GIÁ TRỊ ĐÁP ÁN của một bài toán — kỹ thuật "chặt nhị phân trên đáp án" ở Bài 2.