Binary Search: bãi mìn off-by-one

Ai cũng có một câu chuyện binary search. Của tôi xảy ra trong một buổi phỏng vấn điện thoại, với một mảng đã sắp xếp, và một vòng lặp chạy mãi không thoát vì tôi viết right = mid thay vì right = mid - 1. Tôi biết thuật toán. Tôi đã dùng nó hàng chục lần. Và tôi vẫn viết sai điều kiện biên dưới áp lực. Đó là bản chất của binary search — ý tưởng thì đơn giản, implementation thì không.

Bài toán (LeetCode 704): cho một mảng số nguyên đã sắp xếp và một target, trả về index của target hoặc -1 nếu không tìm thấy. Constraint được nêu rõ — yêu cầu runtime O(log n).

Đọc constraints

Constraints ở đây tối giản, nhưng vẫn định hình cách tiếp cận.

1 <= nums.length <= 10^4. Giới hạn dưới nghĩa là không cần lo về mảng rỗng. Giới hạn trên (10.000 phần tử) đủ nhỏ để ngay cả linear scan cũng chạy trong vài microsecond trên phần cứng hiện đại. Nhưng đề bài yêu cầu O(log n), đó là tiêu chuẩn cần đạt.

-10^4 < nums[i], target < 10^4. Giá trị bị giới hạn, không cần lo overflow cho các phần tử mảng. Dù vậy, phép tính mid-point (lo + hi) vẫn có thể overflow trong các ngôn ngữ có integer kích thước cố định nếu cả hai gần Int32.MaxValue — nói thêm ở phần dưới.

Tất cả số nguyên là duy nhất. Điều này loại bỏ mọi mơ hồ về việc trả về index nào nếu có duplicates. Một kết quả khớp, một câu trả lời.

Mảng được sắp xếp tăng dần. Đây là điều làm cho binary search có thể áp dụng được. Tính chất đã sắp xếp là invariant bạn khai thác — ở mỗi bước, bạn biết target phải nằm ở nửa nào. Không có nó, bạn phải quay về linear scan.

Brute force: O(n)

Cách tiếp cận ngây thơ: duyệt qua từng phần tử theo thứ tự. Khi gặp target, trả về index của nó. Nếu duyệt hết mảng, trả về -1.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

public class Solution {
    public int Search(int[] nums, int target) {
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
}

Cách này hoạt động. Nó bỏ qua hoàn toàn tính chất đã sắp xếp và vi phạm yêu cầu O(log n). Worst case là khi target ở vị trí cuối hoặc vắng mặt, cần duyệt qua toàn bộ n phần tử. Time O(n), space O(1).

Đề bài cấm cách này. Nhưng nó là baseline hữu ích — nếu mảng không được sắp xếp, linear scan là thứ bạn sẽ dùng.

Binary search (iterative): O(log n)

Ý tưởng: cho một mảng đã sắp xếp, bạn có thể tìm bất kỳ target nào trong O(log n) thời gian bằng cách liên tục chia đôi không gian tìm kiếm. Ở mỗi bước, bạn nhìn vào phần tử giữa. Nếu khớp, xong. Nếu target nhỏ hơn, nó phải ở nửa trái. Nếu lớn hơn, nửa phải. Bỏ nửa thua và lặp lại.

Mười lần lặp xử lý được 1.024 phần tử. Hai mươi lần xử lý được một triệu. Đảm bảo O(log n) là có thật và rất ấn tượng.

Đây là template tôi dùng mỗi lần:

class Solution:
    def search(self, 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
            elif nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
 
        return -1

public class Solution {
    public int Search(int[] nums, int target) {
        int lo = 0, hi = nums.Length - 1;
 
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
 
            if (nums[mid] == target)   return mid;
            if (nums[mid] < target)    lo = mid + 1;
            else                       hi = mid - 1;
        }
 
        return -1;
    }
}

lo <= hi. mid + 1 và mid - 1. Vòng lặp thoát sạch khi lo > hi, nghĩa là không gian tìm kiếm đã rỗng. Lúc đó target được xác nhận là vắng mặt, và -1 là đúng.

Trace qua ví dụ đầu tiên

nums = [-1, 0, 3, 5, 9, 12], target = 9. Đi từng bước một.

Dạng văn bản:

lo=0, hi=5  ->  mid=2  ->  nums[2]=3  <  9  ->  lo=3
lo=3, hi=5  ->  mid=4  ->  nums[4]=9  == 9  ->  return 4

Hai lần lặp. Mảng có 6 phần tử. Bắt đầu với 6 ứng viên, cắt còn 3 ở nửa phải, rồi tìm thấy kết quả.

Trace target vắng mặt

nums = [-1, 0, 3, 5, 9, 12], target = 2. Thuật toán phải xác nhận sự vắng mặt mà không xét lại phần tử nào.

lo=0, hi=5  ->  mid=2  ->  nums[2]=3  >  2  ->  hi=1
lo=0, hi=1  ->  mid=0  ->  nums[0]=-1 <  2  ->  lo=1
lo=1, hi=1  ->  mid=1  ->  nums[1]=0  <  2  ->  lo=2
lo=2, hi=1  ->  lo > hi  ->  thoát
return -1

Ba lần lặp, sáu phần tử. Thoát sạch. Không phần tử nào được xét lại. Target vắng mặt tạo ra lo > hi, vòng lặp kết thúc, và -1 là đúng.

Tại sao lo <= hi chứ không phải lo < hi

Câu hỏi <= vs < gây nhầm lẫn vì cả hai đều có thể đúng — chúng chỉ hoạt động theo cách khác nhau, và trộn lẫn quy tắc từ cái này vào cái kia sẽ tạo ra bug.

Với lo <= hi, vòng lặp chạy miễn là còn ít nhất một phần tử cần kiểm tra. Khi lo == hi, bạn vẫn còn một ứng viên. Thân vòng lặp kiểm tra nó. Nếu không phải target, bạn đẩy lo qua hi (hoặc kéo hi qua lo) và thoát. Mỗi phần tử được xét đúng một lần.

Với lo < hi, vòng lặp thoát khi lo == hi, để lại một phần tử chưa được kiểm tra. Nghĩa là bạn phải kiểm tra nums[lo] sau vòng lặp. Điều này ổn nếu bạn luôn nhớ làm. Theo kinh nghiệm của tôi, bạn không phải lúc nào cũng nhớ.

Template lo <= hi là tự đầy đủ. Vòng lặp xử lý mọi phần tử, kể cả trường hợp singleton. Không cần kiểm tra sau vòng lặp. Tôi chọn nó từ nhiều năm trước và chưa bao giờ đổi.

Cách tính mid

mid = lo + (hi - lo) // 2

Không phải (lo + hi) // 2. Trong Python điều này hiếm khi quan trọng vì integer không bị overflow. Trong C# (và Java, C++) thì có: lo + hi có thể overflow int nếu cả hai gần Int32.MaxValue. lo + (hi - lo) / 2 về mặt toán học tương đương nhưng an toàn — hi - lo luôn không âm và bị giới hạn bởi độ dài mảng.

Thói quen được đền đáp ở đây. Viết theo cách an toàn và bạn không bao giờ phải nghĩ về nó nữa.

Điều gì xảy ra khi bỏ lỡ

Đây là nơi hầu hết các implementation đi sai.

Khi nums[mid] < target, bạn biết target nằm hoàn toàn ở bên phải của mid. Không gian tìm kiếm tiếp theo bắt đầu từ mid + 1. Nếu bạn viết lo = mid, bạn đưa mid vào lần lặp tiếp theo dù đã loại trừ nó — và nếu lo == hi == mid, bạn bị kẹt trong vòng lặp vô tận.

Khi nums[mid] > target, lý luận đối xứng: không gian tìm kiếm tiếp theo kết thúc ở mid - 1. Viết hi = mid - 1.

Luôn loại trừ mid khi bỏ lỡ. Đó là invariant. Vi phạm nó và bạn sẽ có vòng lặp vô tận hoặc bỏ sót phần tử.

Biến thể lo < hi cho bài toán tìm boundary

Template này tồn tại, hợp lệ, và bạn sẽ thấy nó trong nhiều editorial solution cho bài toán tìm boundary. Dạng đầy đủ cho bài toán khớp chính xác:

lo, hi = 0, len(nums) - 1
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid          # KHÔNG phải mid - 1
return nums[lo] if nums[lo] == target else -1

public class Solution {
    public int Search(int[] nums, int target) {
        int lo = 0, hi = nums.Length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < target) lo = mid + 1;
            else                    hi = mid;   // KHÔNG phải mid - 1
        }
        return nums[lo] == target ? lo : -1;
    }
}

Sự khác biệt chính: trên nhánh nums[mid] >= target, bạn viết hi = mid thay vì hi = mid - 1. Điều này an toàn vì lo < hi đảm bảo mid < hi, vì vậy hi = mid vẫn thu nhỏ cửa sổ. Vòng lặp thoát với lo == hi, và bạn kiểm tra một phần tử còn lại đó sau vòng lặp.

Tại sao template này tồn tại? Nó hữu ích khi bạn đang tìm kiếm một boundary — index ngoài cùng bên trái nơi một điều kiện nào đó đầu tiên đúng — thay vì khớp chính xác. Vòng lặp lo < hi thoát ra trỏ vào đáp án thay vì bước qua nó.

Cho bài toán này, lo <= hi gọn hơn và tôi sẽ dùng nó. Nhưng bạn nên biết cả hai, vì các bài boundary-finding cần form này và bài phỏng vấn hay dùng dạng đó.

Binary search (recursive): O(log n)

Cũng có thể implement binary search theo dạng recursion. Base case là không gian tìm kiếm rỗng (lo > hi); recursive case là ba nhánh điều kiện tương tự.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        def bs(lo, hi):
            if lo > hi:
                return -1
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                return bs(mid + 1, hi)
            return bs(lo, mid - 1)
        return bs(0, len(nums) - 1)

public class Solution {
    public int Search(int[] nums, int target) => Bs(nums, target, 0, nums.Length - 1);
 
    private int Bs(int[] nums, int target, int lo, int hi) {
        if (lo > hi) return -1;
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target)  return Bs(nums, target, mid + 1, hi);
        return Bs(nums, target, lo, mid - 1);
    }
}

O(log n) time, O(log n) stack space. Với constraint của bài này, call depth tối đa là log2(10^4) ≈ 14 frame — không có nguy cơ stack overflow. Nhưng không có lý do thực tế nào để ưu tiên cách này so với phiên bản iterative. Dạng iterative ngắn hơn, nhanh hơn, và có O(1) space. Tôi chỉ viết recursion ở đây nếu cấu trúc dữ liệu tự nhiên yêu cầu nó. Với bài này, đây là công cụ giảng dạy, không phải lựa chọn production.

So sánh các approach

Các edge case thực sự quan trọng

Một phần tử, target có mặt. nums = [5], target = 5. lo=0, hi=0. mid=0. nums[0] == 5. Return 0. Dấu <= trong while lo <= hi chính xác là thứ làm cho singleton hoạt động — thân vòng lặp chạy một lần cho lo == hi.

Một phần tử, target vắng mặt. nums = [5], target = 3. mid=0. nums[0]=5 > 3. hi = -1. Ngay lần kiểm tra tiếp theo lo=0 > hi=-1 — điều kiện thất bại, vòng lặp thoát. Return -1.

Target nhỏ hơn mọi phần tử. nums = [3, 5, 9], target = 1. Mid đầu tiên cho nums[mid] > 1, nên hi rơi xuống dưới lo sau một bước. Return -1. Không cần trường hợp đặc biệt.

Target lớn hơn mọi phần tử. nums = [3, 5, 9], target = 11. Mỗi mid so sánh nhỏ hơn target, nên lo leo lên đến khi vượt hi. Return -1. Đối xứng với trường hợp trên.

Target ở index 0. nums = [1, 2, 3], target = 1. Phép tính mid cuối cùng đến index 0 qua quá trình thu hẹp bình thường — không cần xử lý đặc biệt.

Target ở index cuối. nums = [1, 2, 3], target = 3. Đối xứng. Nửa phải tiếp tục được chọn cho đến khi mid đến index cuối.

Không trường hợp nào trong số này cần xử lý đặc biệt. Vòng lặp lo <= hi hấp thụ tất cả vì invariant vẫn giữ: khi không gian tìm kiếm trở nên rỗng, lo > hi, và vòng lặp thoát sạch.

Nhận diện pattern và khi nào nên dùng

Binary search được kích hoạt khi bạn thấy cấu trúc đã sắp xếp và bài toán tìm kiếm. Các tín hiệu rõ ràng nhất:

• Input được sắp xếp (tăng hoặc giảm dần) hoặc có thứ tự đơn điệu theo cách nào đó.
• Bài toán yêu cầu O(log n) tường minh.
• Bạn đang tìm kiếm một phần tử, một vị trí, hoặc một giá trị boundary.

Các tín hiệu ít rõ ràng hơn xuất hiện trong các bài khó hơn: tìm kiếm trên không gian đáp án (binary search trên số nguyên, không phải trên mảng), hoặc các bài toán mà không gian tìm kiếm là đơn điệu ngầm dù mảng không phải vậy (ví dụ: mảng bị xoay vẫn giữ tính chất đã sắp xếp ở từng nửa — bạn chỉ cần xác định nửa nào).

Mental model nền tảng là: "Tôi luôn có thể loại bỏ một nửa ứng viên còn lại chỉ bằng một phép so sánh." Đó là invariant làm cho O(log n) khả thi. Miễn là bạn có thể diễn đạt điều kiện của mình theo dạng phân vùng không gian sạch như vậy, binary search có thể áp dụng.

Series này đi về đâu tiếp theo

Binary search trên mảng một chiều đã sắp xếp là pattern nền tảng. Các bài tiếp theo áp dụng cùng ý tưởng cốt lõi cho những bài toán che giấu cấu trúc đã sắp xếp: một matrix có thể tìm kiếm như một mảng phẳng, một mảng bị xoay nơi tính chất đã sắp xếp được giữ nguyên từng phần, và một dải số nguyên nơi bạn binary search trên chính đáp án.

Các bài liên quan đáng giải tiếp theo:

• Search a 2D Matrix (74) — các hàng của matrix đã được sắp xếp và phần tử cuối của mỗi hàng nhỏ hơn phần tử đầu của hàng tiếp theo. Toàn bộ matrix có thể được coi là một dãy đã sắp xếp, sau đó binary search với index arithmetic.
• Find Minimum in Rotated Sorted Array (153) — mảng đã sắp xếp, rồi bị xoay. Binary search vẫn áp dụng được; điều kiện phân chia thay đổi từ "so sánh với target" sang "so sánh với biên phải."
• Search in Rotated Sorted Array (33) — tìm target trong mảng bị xoay. Bạn binary search xem nửa nào vẫn còn được sắp xếp, rồi đi vào nó.
• Search Insert Position (35) — tìm vị trí chèn một giá trị vào mảng đã sắp xếp. Template lo < hi xử lý điều này tự nhiên hơn lo <= hi.
• First Bad Version (278) — binary search trên một dải số nguyên, không phải mảng. Cùng template, không gian tìm kiếm khác.