Chương 5 - Binary Search

Binary Search (tìm kiếm nhị phân) tưởng dễ - “chia đôi mảng đã sort” - nhưng thực tế là bug magnet số một trong phỏng vấn. Knuth từng viết: “trong khi ý tưởng đơn giản, viết đúng nó là chuyện khó hơn ta tưởng”. Chương này dạy bạn một template duy nhất áp dụng cho mọi biến thể: tìm equal, tìm boundary, tìm trên rotated, search on answer, … - sẽ gặp lại ở Chương 25 (Advanced Binary Search).

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Thuộc 1 template duy nhất cho mọi biến thể (half-open [lo, hi)).
  • Phân biệt: tìm equal / lower_bound / upper_bound / first True / last False.
  • Nhận diện đặc tính monotonic predicate (gateway cho Ch 25).
  • Tránh bẫy off-by-one và infinite loop.

Khi nào dùng pattern này?

  • Có cấu trúc đơn điệu (sorted hoặc có thể “search on answer”).
  • Đề bài yêu cầu O(log n) hoặc gợi ý dùng search.
  • Yêu cầu tìm boundary (first / last occurrence, insert position, …).
  • Khi không gian tìm kiếm có thể đại diện bởi 1 đoạn [lo, hi] và bài chia được thành 2 nửa “có đáp án” / “không có đáp án”.

Mẫu suy nghĩ chuẩn: 1. Không gian tìm kiếm là gì? (index, giá trị, đáp án). 2. Hàm check(mid) trả True/False thế nào? Liệu nó đơn điệu không? 3. Đáp án là ranh giới nào? First True hay last False?

Template code 

def lower_bound(nums: list[int], target: int) -> int:
    """Trả về vị trí đầu tiên có nums[i] >= target. Nếu không có, trả về len(nums)."""
    lo, hi = 0, len(nums)        # [lo, hi)  - half-open
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def upper_bound(nums: list[int], target: int) -> int:
    """Trả về vị trí đầu tiên có nums[i] > target."""
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def binary_search_answer(check, lo: int, hi: int) -> int:
    """Tìm giá trị nhỏ nhất trong [lo, hi] thoả check(x)=True (check đơn điệu F→T)."""
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Mẹo cuối cùng: mình luôn dùng nửa khoảng đóng-mở [lo, hi) và điều kiện vòng lặp lo < hi. Cách này đồng bộ với bisect của Python và ít bug off-by-one hơn cách lo <= hi.

Bài tự luyện cuối chương

  • LC 162 - Find Peak Element
  • LC 153 - Find Minimum in Rotated Sorted Array
  • LC 540 - Single Element in a Sorted Array
  • LC 658 - Find K Closest Elements
  • LC 1011 - Capacity To Ship Packages Within D Days (Chương 25)
  • LC 875 - Koko Eating Bananas (Chương 25)

5.1 Binary Search cơ bản (LC 704)

Đề bài

Cho mảng nums đã sort tăng dần và số target. Trả về chỉ số của target trong nums, hoặc -1 nếu không có. Phải chạy O(log n).

Ví dụ 

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

Ràng buộc

  • 1 <= len(nums) <= 10^4
  • -10^4 < nums[i], target < 10^4
  • Tất cả nums[i] phân biệt và đã sort tăng dần.

Clarifying questions

  • Có duplicate không? → Theo đề: không. Nếu có thì hỏi: trả về index nào (first/last/any)?
  • Sort tăng hay giảm? → Tăng. Nếu giảm, ta đảo dấu so sánh.

Hướng tiếp cận

Brute force - O(n). Duyệt tuần tự - không thoả O(log n).

Tối ưu - Binary Search half-open, O(log n).

Duy trì [lo, hi). Tại mỗi vòng: - mid = (lo + hi) // 2. - Nếu nums[mid] == target → trả mid. - Nếu nums[mid] < target → đáp án (nếu có) ở [mid+1, hi) → lo = mid + 1. - Nếu nums[mid] > target → đáp án ở [lo, mid) → hi = mid.

Hình minh hoạ với nums = [-1, 0, 3, 5, 9, 12], target = 9:

index :     0    1    2    3    4    5
nums  :  [ -1,   0,   3,   5,   9,  12 ]

Vòng 1: lo=0, hi=6  → mid=3, nums[3]=5 < 9 → lo = mid+1 = 4
Vòng 2: lo=4, hi=6  → mid=5, nums[5]=12 > 9 → hi = mid = 5
Vòng 3: lo=4, hi=5  → mid=4, nums[4]=9 == 9 → trả 4  ✓

Code Python 3 

from typing import List

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

Phân tích độ phức tạp

  • Thời gian: O(log n).
  • Bộ nhớ: O(1).

Bình luận

  • Bẫy thường gặp:
    • Overflow (lo + hi) // 2 - Python int không bị, nhưng C/C++/Java dùng lo + (hi - lo) // 2 để an toàn.
    • Off-by-one giữa [lo, hi] (đóng-đóng) và [lo, hi) (đóng-mở) - chọn 1 cách, dùng kiên định cho mọi bài.
    • Vòng lặp không tiến → infinite loop. Luôn đảm bảo mỗi vòng giảm khoảng tìm kiếm.
  • Pattern half-open: đẹp ở chỗ hi luôn không bao gồm - cùng convention với range() và bisect của Python.
  • Follow-up:
    1. Mảng có duplicate → tìm first/last occurrence (bài 5.4).
    2. Mảng cycled/rotated → bài 5.5.
    3. Mảng 2D đã sort → LC 74 (mỗi hàng + giữa các hàng cùng tăng).

Bài tự luyện liên quan

  • LC 35 - Search Insert Position (bài 5.2).
  • LC 74 - Search a 2D Matrix.
  • LC 374 - Guess Number Higher or Lower.

5.2 Search Insert Position (LC 35)

Đề bài

Cho mảng nums đã sort, không có duplicate, và target. Trả về: - Chỉ số của target nếu có trong mảng. - Vị trí mà target sẽ được chèn vào nếu không có (giữ mảng vẫn sort).

Phải O(log n).

Ví dụ 

Input:  nums = [1, 3, 5, 6], target = 5   → 2
Input:  nums = [1, 3, 5, 6], target = 2   → 1
Input:  nums = [1, 3, 5, 6], target = 7   → 4   (chèn cuối)
Input:  nums = [1, 3, 5, 6], target = 0   → 0   (chèn đầu)

Ràng buộc

  • 1 <= len(nums) <= 10^4
  • -10^4 <= nums[i], target <= 10^4
  • nums sort tăng dần, không duplicate.

Clarifying questions

  • Nếu có duplicate? → Đề loại trừ, nhưng pattern này tự nhiên trả về vị trí lower_bound.

Hướng tiếp cận

Đây chính là lower_bound! Vị trí đầu tiên có nums[i] >= target - ý nghĩa: “đây là vị trí target sẽ đứng nếu được chèn”.

Code Python 3 

from typing import List

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

Phân tích độ phức tạp

  • Thời gian: O(log n).
  • Bộ nhớ: O(1).

Bình luận

  • So với bài 5.1: Y hệt template lower_bound. Bài 5.1 trả -1 nếu không thấy, bài này luôn trả về vị trí - đó là khác biệt duy nhất.
  • 1 dòng giải: return bisect.bisect_left(nums, target). Khi phỏng vấn, hãy code “tay” template trước, rồi mới đề cập bisect.
  • Edge cases bắt buộc test:
    • target nhỏ hơn tất cả → trả 0.
    • target lớn hơn tất cả → trả len(nums).
    • Mảng 1 phần tử.

Bài tự luyện liên quan

  • LC 704 - Binary Search.
  • LC 540 - Single Element in a Sorted Array.
  • LC 33 - Search in Rotated Sorted Array (bài 5.5).

5.3 First Bad Version (LC 278)

Đề bài

Cho n phiên bản, đánh số từ 1 đến n. Có một phiên bản “bad” và mọi phiên bản sau nó cũng bad. Bạn được cấp hàm API isBadVersion(int) trả True/False. Hãy tìm phiên bản bad đầu tiên với số lần gọi API tối thiểu.

Ví dụ 

n = 5, bad version = 4
gọi isBadVersion(3) → False
gọi isBadVersion(5) → True
gọi isBadVersion(4) → True
→ trả 4

Ràng buộc

  • 1 <= bad <= n <= 2^31 - 1

Clarifying questions

  • API có cost thật không? → Coi như có. Mục tiêu: gọi O(log n) lần.
  • Mảng [False, ..., False, True, ..., True] là *đơn điệu → áp được binary search.*

Hướng tiếp cận

Đây là search on monotonic predicate. Pattern hoàn hảo cho template binary_search_answer:

  • check(v) = isBadVersion(v) - đơn điệu False → True.
  • Đáp án = vị trí đầu tiên check thành True.

Hình minh hoạ với n = 7, bad = 4:

version :  1     2     3     4     5     6     7
check  :   F     F     F     T     T     T     T
                              ↑
                       cần tìm vị trí này

Vòng 1: lo=1, hi=7  → mid=4, check(4)=T → hi=4
Vòng 2: lo=1, hi=4  → mid=2, check(2)=F → lo=3
Vòng 3: lo=3, hi=4  → mid=3, check(3)=F → lo=4
lo == hi → trả lo = 4  ✓

Code Python 3 

def isBadVersion(v: int) -> bool: ...     # API có sẵn

class Solution:
    def firstBadVersion(self, n: int) -> int:
        lo, hi = 1, n      # closed interval [lo, hi]
        while lo < hi:
            mid = lo + (hi - lo) // 2      # tránh overflow ở các ngôn ngữ khác
            if isBadVersion(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

Phân tích độ phức tạp

  • Thời gian: O(log n) lần gọi API.
  • Bộ nhớ: O(1).

Bình luận

  • Tại sao dùng lo + (hi - lo) // 2? Trong Java/C++, lo + hi có thể vượt INT_MAX. Python int vô hạn nên không vấn đề, nhưng đây là good habit vì bạn có thể phỏng vấn ngôn ngữ khác. Cách viết này dễ trở thành thói quen.
  • Bẫy thường gặp:
    • Khởi tạo hi = n + 1 (như half-open) - sẽ gọi isBadVersion(n + 1) → out of range. Phải dùng closed [1, n].
    • Quên trường hợp toàn bộ True (bad từ version 1) hoặc toàn bộ False (đề bài đảm bảo không xảy ra, nhưng vẫn nên check).
  • Pattern “first True”: Bài này dạy bạn cách áp binary search cho mọi hàm check đơn điệu - kỹ thuật cốt lõi của Chương 25.

Bài tự luyện liên quan

  • LC 162 - Find Peak Element.
  • LC 1011 - Capacity To Ship Packages Within D Days.
  • LC 875 - Koko Eating Bananas.

5.4 Find First and Last Position of Element (LC 34)

Đề bài

Cho mảng nums đã sort tăng dần (có thể có duplicate) và target. Trả về [first, last] - chỉ số đầu và cuối của các vị trí target trong mảng. Nếu không có, trả [-1, -1]. Phải O(log n).

Ví dụ 

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

Input:  nums = [5, 7, 7, 8, 8, 10], target = 6
Output: [-1, -1]

Input:  nums = [], target = 0
Output: [-1, -1]

Ràng buộc

  • 0 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

Clarifying questions

  • Sort tăng? → Theo đề: tăng (cho phép duplicate).
  • Output cho trường hợp không có target? → [-1, -1].

Hướng tiếp cận

Dùng 2 lần binary search: - first = lower_bound(target) - vị trí đầu tiên >= target. - last = upper_bound(target) - 1 - vị trí cuối cùng <= target.

Sau đó kiểm tra xem first có hợp lệ và nums[first] == target không.

Hình minh hoạ với nums = [5, 7, 7, 8, 8, 10], target = 8:

index :     0    1    2    3    4    5
nums  :  [  5,   7,   7,   8,   8,  10 ]
                          ↑    ↑
                       first  last

lower_bound(8) = 3   (vị trí đầu tiên >= 8)
upper_bound(8) = 5   (vị trí đầu tiên > 8)
last           = 4   (= upper - 1)

Trả [3, 4]

Code Python 3 

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound(t: int) -> int:
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < t:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

        first = lower_bound(target)
        if first == len(nums) or nums[first] != target:
            return [-1, -1]
        last = lower_bound(target + 1) - 1
        return [first, last]

Phân tích độ phức tạp

  • Thời gian: O(log n) - 2 lần binary search độc lập.
  • Bộ nhớ: O(1).

Bình luận

  • Mẹo: upper_bound(t) == lower_bound(t + 1) với mảng số nguyên. Mình tận dụng để chỉ phải viết 1 hàm lower_bound.
  • Bẫy thường gặp:
    • Quên check first == len(nums) → IndexError khi target lớn hơn mọi phần tử.
    • Không check nums[first] == target → trả về [first, first - 1] sai khi target không tồn tại.
  • Follow-up phổ biến:
    1. Đếm số lần xuất hiện của target? → last - first + 1 (nếu first hợp lệ).
    2. LC 540 - Single Element in a Sorted Array: parity trick.
    3. LC 33 - Search in Rotated Sorted Array (bài 5.5).

Bài tự luyện liên quan

  • LC 35 - Search Insert Position.
  • LC 540 - Single Element in a Sorted Array.
  • LC 658 - Find K Closest Elements.

5.5 Search in Rotated Sorted Array (LC 33)

Đề bài

Cho mảng nums đã sort tăng dần và các giá trị phân biệt, sau đó bị xoay tại một pivot bí ẩn (k lần xoay phải, k chưa biết). Cho target, trả về index hoặc -1. Phải O(log n).

Ví dụ 

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

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

Input:  nums = [1], target = 0
Output: -1

Ràng buộc

  • 1 <= len(nums) <= 5000
  • -10^4 <= nums[i] <= 10^4
  • Tất cả phân biệt.
  • nums đã được xoay tại một pivot không biết trước.

Clarifying questions

  • Có duplicate không? → Theo đề: không. (LC 81 mới có duplicate, khó hơn một chút.)
  • Có cần trả về *một index hay tất cả?* → Bất kỳ index nào hợp lệ.

Hướng tiếp cận

Quan sát then chốt: Khi chia mảng bị rotated tại mid, luôn có ít nhất một nửa ([lo, mid] hoặc [mid, hi]) là sorted đúng (không bị rotate).

Quy trình mỗi vòng: 1. Tính mid. 2. Nếu nums[mid] == target → trả mid. 3. Xác định nửa nào đang sorted: - Nếu nums[lo] <= nums[mid] → nửa trái sorted. - Ngược lại → nửa phải sorted. 4. Kiểm tra target có nằm trong nửa sorted không (so sánh bằng <, >): - Có → search nửa sorted. - Không → search nửa còn lại.

Hình minh hoạ với nums = [4, 5, 6, 7, 0, 1, 2], target = 0:

index :   0    1    2    3    4    5    6
nums  :  [4,   5,   6,   7,   0,   1,   2]
          lo                            hi

Vòng 1: lo=0, hi=6, mid=3, nums[mid]=7
  nums[lo]=4 <= nums[mid]=7 → nửa trái [0..3] = [4,5,6,7] đã sort.
  target=0 nằm trong [4..7]? Không (0 < 4) → đi nửa phải.
  → lo = mid + 1 = 4

Vòng 2: lo=4, hi=6, mid=5, nums[mid]=1
  nums[lo]=0 <= nums[mid]=1 → nửa trái [4..5] = [0,1] đã sort.
  target=0 nằm trong [0..1]? Có → đi nửa trái.
  → hi = mid - 1 = 4

Vòng 3: lo=4, hi=4, mid=4, nums[mid]=0 == target → trả 4  ✓

Code Python 3 

from typing import List

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

            # Nửa trái [lo..mid] đã sort?
            if nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1     # target ở nửa trái
                else:
                    lo = mid + 1
            # Ngược lại: nửa phải [mid..hi] đã sort
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1     # target ở nửa phải
                else:
                    hi = mid - 1

        return -1

Phân tích độ phức tạp

  • Thời gian: O(log n).
  • Bộ nhớ: O(1).

Bình luận

  • Bẫy thường gặp:
    • Bất đẳng thức nhầm dấu <= / < ở các điều kiện biên - luôn chạy thử bằng ví dụ nhỏ để kiểm chứng.
    • Quên xử lý trường hợp nums[lo] == nums[mid] (rotated nhưng 2 phần tử kề bằng). Với mảng phân biệt thì OK vì điều kiện <= đảm bảo “nửa trái sort”.
  • Có cách nào “thẳng” hơn không? Có - tìm trước pivot (index nhỏ nhất) bằng binary search, rồi binary search bình thường trong nửa chứa target. Nhưng phải gọi search 2 lần, không hơn.
  • Follow-up phổ biến:
    1. LC 81 - Search in Rotated Sorted Array II: có duplicate. Khi nums[lo] == nums[mid] == nums[hi] ta không phân biệt được nửa nào sort → fallback lo += 1, hi -= 1 (worst O(n)).
    2. LC 153 - Find Minimum in Rotated Sorted Array: tìm pivot.
    3. LC 4 - Median of Two Sorted Arrays (Chương 25).

Bài tự luyện liên quan

  • LC 81 - Search in Rotated Sorted Array II.
  • LC 153 - Find Minimum in Rotated Sorted Array.
  • LC 154 - Find Minimum in Rotated Sorted Array II.

5.6 Sqrt(x) (LC 69)

Đề bài

Cho số nguyên không âm x. Trả về căn bậc hai làm tròn xuống của x, tức là số nguyên r lớn nhất sao cho r * r <= x.

Không được dùng hàm built-in sqrt.

Ví dụ 

Input:  x = 4   → 2
Input:  x = 8   → 2   (vì 2² = 4 ≤ 8 < 9 = 3²)
Input:  x = 0   → 0
Input:  x = 1   → 1

Ràng buộc

  • 0 <= x <= 2^31 - 1

Clarifying questions

  • Trả số nguyên hay số thực? → Số nguyên (làm tròn xuống).
  • Có cho phép dùng pow? → Theo tinh thần đề: không. Bài muốn test binary search hoặc Newton’s method.

Hướng tiếp cận

Cách 1 - Binary Search trên đáp án - O(log x).

Tìm số nguyên lớn nhất r thoả r² <= x. Tương đương với “last True” trong dãy đơn điệu [T, T, ..., T, F, F, ...] (T = r² <= x).

Khoảng tìm kiếm: [0, x] (hoặc [0, x//2 + 1] để tiết kiệm).

Cách 2 - Newton’s Method - O(log x) nhưng hằng số nhỏ hơn.

Lặp r = (r + x/r) / 2 cho đến khi r² <= x < (r+1)². Hội tụ rất nhanh (quadratic convergence) - đây là cách sqrt được cài trong nhiều thư viện chuẩn.

Hình minh hoạ - Binary Search cho x = 8:

   r :    0    1    2    3    4    5    6    7    8
  r² :    0    1    4    9   16   25   36   49   64
                    ↑
                last r với r² <= 8

Vòng 1: lo=0, hi=8   mid=4, 16 > 8 → hi = 3
Vòng 2: lo=0, hi=3   mid=1,  1 <= 8 → answer=1, lo=2
Vòng 3: lo=2, hi=3   mid=2,  4 <= 8 → answer=2, lo=3
Vòng 4: lo=3, hi=3   mid=3,  9 > 8 → hi=2  → lo > hi, dừng

Trả 2  ✓

Code Python 3 

class Solution:
    """Cách 1 - Binary Search."""

    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        lo, hi = 1, x // 2 + 1
        answer = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= x:
                answer = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return answer


class SolutionNewton:
    """Cách 2 - Newton's Method, hằng số nhỏ hơn."""

    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        r = x
        while r * r > x:
            r = (r + x // r) // 2
        return r

Phân tích độ phức tạp

  • Cách 1: O(log x) time, O(1) space.
  • Cách 2: Cũng O(log x) worst case, nhưng số bước thực tế rất ít (quadratic convergence, ~ 5 bước cho x = 10^9).

Bình luận

  • Bẫy thường gặp:
    • Để lo = 0 ban đầu nhưng quên xử lý x = 0 → vòng lặp 0 * 0 == 0 <= 0 có thể trả 0, nhưng tốt nhất check riêng x < 2.
    • mid * mid overflow ở các ngôn ngữ 32-bit (Python an toàn) - cần (long long)mid * mid hoặc so sánh mid <= x // mid.
  • Newton’s intuition: mỗi bước lấy trung bình của r và x / r. Đáp số thật r* ở giữa hai số này → trung bình tiến gần hơn r*. Sự hội tụ là bậc 2 (số đúng nhân đôi mỗi vòng).
  • Follow-up phổ biến:
    1. Sqrt thực với độ chính xác epsilon → vẫn dùng binary search trên [0, x] với float, dừng khi hi - lo < eps.
    2. Căn bậc k - LC 50 (Pow) ngược lại bằng Newton tổng quát.
    3. LC 367 - Valid Perfect Square.

Bài tự luyện liên quan

  • LC 367 - Valid Perfect Square.
  • LC 50 - Pow(x, n).
  • LC 633 - Sum of Square Numbers.

Tóm tắt chương & Quyết định

Template invariants (chọn 1 và bám)

Closed interval [lo, hi]:

lo, hi = 0, n - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if check(mid): return mid
    elif too_small(mid): lo = mid + 1
    else: hi = mid - 1
return -1

Half-open [lo, hi) - first-true (lower_bound):

lo, hi = 0, n          # hi không inclusive
while lo < hi:
    mid = (lo + hi) // 2
    if pred(mid): hi = mid
    else: lo = mid + 1
return lo                # vị trí đầu tiên thỏa
  • Invariant với first-true: pred(mid) là True ở [lo..hi) cuối cùng; vị trí trả về là vị trí True đầu tiên hoặc n nếu không có.

Checklist trước khi submit

  1. lo, hi khởi tạo đúng (đặc biệt khi search on answer: lo = min, hi = max hoặc max+1).
  2. Điều kiện vòng lặp khớp với loại interval (<= hay <).
  3. Cập nhật mid+1 / mid-1 / mid đúng - tránh infinite loop.
  4. Trường hợp không tìm thấy trả về cái gì? -1, n, lo?
  5. Overflow (lo + hi) // 2 an toàn ở Python; ở Java/C++ dùng lo + (hi - lo) // 2.

Sqrt overflow note (ngôn ngữ khác)

Python int không tràn. Java/C++: mid * mid có thể tràn int32. Dùng (long) mid * mid hoặc so sánh mid <= x / mid để tránh nhân.