Tìm kiếm nhị phân: mỗi bước loại một nửa nhưng dữ liệu phải có thứ tự

💻 Làm sao tìm nhanh trong một triệu mục?

Nếu danh sách đã sắp xếp, so sánh với phần tử giữa cho biết mục tiêu chỉ có thể ở nửa trái hay nửa phải. Mỗi bước làm đoạn ứng viên giảm gần một nửa.

Khung thuật toán

• Đặt left=0, right=n−1.
• Khi left≤right, lấy mid=left+⌊(right−left)/2⌋.
• Nếu a[mid] nhỏ hơn mục tiêu, đặt left=mid+1; nếu lớn hơn, đặt right=mid−1.

Độ phức tạp

Sau k bước còn khoảng n/2ᵏ ứng viên, nên số so sánh tăng theo O(log n). Nhưng nếu dữ liệu chưa sắp xếp và chỉ tìm một lần, chi phí sắp xếp có thể lớn hơn lợi ích.

⚠️ Lỗi biên

Quên dấu bằng trong left≤right hoặc không cộng/trừ 1 khi cập nhật có thể bỏ sót phần tử cuối hay tạo vòng lặp vô hạn.

🔎 Vết chạy

Lập bảng left, mid, right, giá trị so sánh sau từng bước và kiểm tra đoạn thực sự nhỏ đi.