Chuyển tới nội dung chính

Tìm Kiếm Nhị Phân (Binary Search)

Bạn sẽ học được gì

Cách tìm một phần tử trong mảng đã sắp xếp với độ phức tạp O(log n) thay vì O(n), và — quan trọng hơn — nhận ra khi nào một bài toán có thể giải bằng tìm kiếm nhị phân.

1. Trực quan: tại sao lại "nhị phân"?​

Tưởng tượng bạn tra một từ trong từ điển 1000 trang. Bạn không lật từng trang. Bạn mở giữa, thấy từ cần tìm nằm trước hay sau, rồi bỏ đi một nửa. Lặp lại — mỗi bước loại bỏ một nửa số trang còn lại. Đó chính là tìm kiếm nhị phân.

Bấm Play để xem từng bước thu hẹp khoảng [L, R]:

🎬 Trực quan hóa: binary_search(arr, 11) · Bước 1/2
1
L
3
5
7
M
9
11
13
R
arr[3] = 7 < mục tiêu → bỏ nửa trái, left = 4

Component này do dự án tự xây theo mô hình Algorithm Visualizer (license MIT).

2. Khái niệm & nguyên lý​

Điều kiện tiên quyết: mảng phải đã được sắp xếp.

Ta duy trì khoảng [left, right]. Mỗi bước:

  1. Tính mid = left + (right - left) // 2 (tránh tràn số).
  2. So sánh arr[mid] với target:
    • Bằng → tìm thấy.
    • arr[mid] < target → left = mid + 1 (tìm nửa phải).
    • arr[mid] > target → right = mid - 1 (tìm nửa trái).
  3. Lặp đến khi left > right → không tìm thấy.
Ba lỗi kinh điển
  1. Quên mảng phải sắp xếp.
  2. Vòng lặp vô hạn — quên +1/-1 khi cập nhật biên.
  3. Tràn số — dùng (left + right) // 2 với mảng cực lớn.

3. Code mẫu (chạy trực tiếp)​

Đang tải trình chạy code…
🎬 Trực quan hóa tương tác — VisuAlgo
Nhập mảng và target tùy ý, theo dõi L/R/mid thu hẹp từng bước. Thử target không tồn tại để xem khi nào L > R.
Nguồn: visualgo.net — Steven Halim, NUS. Dùng cho lớp học; ảnh chụp/video cần ghi nguồn URL.

4. Độ phức tạp​

Độ phức tạpGiải thích
Thời gianO(log n)Mỗi bước loại bỏ một nửa → tối đa log₂(n) bước
Bộ nhớO(1)Bản lặp chỉ dùng vài biến

Với mảng 1 tỷ phần tử, binary search chỉ cần ~30 bước (2³⁰ ≈ 10⁹).

💡 Học cách nhận ra mẫu, không học thuộc lời giải.

  • Dữ liệu đã sắp xếp và cần tìm kiếm nhanh.
  • Bài toán hỏi "giá trị nhỏ nhất/lớn nhất thỏa điều kiện X" có tính đơn điệu → binary search trên đáp án.
  • Cần tìm biên (phần tử đầu/cuối thỏa một điều kiện).

Khung mẫu tổng quát:

  1. Xác định không gian tìm kiếm [lo, hi].
  2. Xác định hàm check(mid) đơn điệu (True/False).
  3. Thu hẹp [lo, hi] đến khi hội tụ.

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

Bài 1 (Cơ bản): Tìm chỉ số đầu tiên của target nếu xuất hiện nhiều lần.

Gợi ý: Khi arr[mid] == target, ghi nhớ mid rồi tiếp tục tìm về bên trái (right = mid - 1).

def first_occurrence(arr, target):
    left, right, ans = 0, len(arr) - 1, -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            ans = mid
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return ans
Bài 2 (Vận dụng): Tìm căn bậc hai làm tròn xuống của x mà không dùng sqrt.

Gợi ý: Binary search trên đáp án. Không gian [0, x], điều kiện đơn điệu mid * mid <= x.

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Điều kiện BẮT BUỘC để dùng tìm kiếm nhị phân là gì?
2. Độ phức tạp thời gian của tìm kiếm nhị phân là?
3. Vì sao nên viết mid = left + (right - left) // 2?
📚 Đọc thêm & Luyện tập
🎬 Video
🏋️ Luyện tập

8. Hoàn thành​

…

☑️ Đánh dấu hoàn thành để lưu tiến độ (localStorage — đồng bộ tài khoản ở Phase 2).