Tìm kiếm nhị phân — Binary Search
Tìm kiếm nhị phân cắt đôi không gian tìm kiếm sau mỗi bước, đạt O(log n) trên dữ liệu đã sắp xếp hoặc trên một miền có tính đơn điệu.
Ngoài việc tìm một phần tử, nó còn dùng để tìm "biên" (phần tử đầu tiên hoặc cuối cùng thoả điều kiện) và cả "tìm kiếm nhị phân trên đáp án". Cái bẫy lớn nhất là off-by-one ở biên và điều kiện dừng — hãy cố định một quy ước khoảng (đóng hay nửa mở) rồi dùng nhất quán.
Tra từ điển — mở giữa, biết phía nào thì cắt nửa kia.
- Mỗi bước cắt phân nửa không gian → O(log n).
- Mảng phải được sắp xếp trước, đổi lại lấy tốc độ tìm kiếm rất nhanh.
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Tìm kiếm nhị phân
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| mảng đã sắp xếp | Điều kiện tiên quyết của binary search |
| tìm vị trí chèn | Biến thể lower-bound |
| min / max thoả điều kiện | Binary search trên không gian đáp án |
| gợi ý O(log n) | Đề nêu rõ độ phức tạp → cắt đôi |
Khi nào dùng
3 tình huống điển hình cần nghĩ đến chủ đề này
Mảng / danh sách đã được sắp xếp và cần tìm một giá trị
Cần tìm vị trí của phần tử hoặc biên của một tập hợp thỏa điều kiện
Bài toán có thể quy về dạng: "tìm giá trị nhỏ / lớn nhất thỏa X"
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Mảng chưa sorted và không thể sort (cần giữ index gốc): dùng Hash Map hoặc linear scan
Dữ liệu rất nhỏ (n < 100): linear search code ngắn, hằng số nhỏ hơn — Binary Search overkill
Predicate không monotonic (không thể "đi 1 hướng" theo đáp án): Binary Search không áp dụng
Hình minh hoạ
Chỉnh dữ liệu rồi bấm Phát để xem từng bước.
let low=0, high=nums.length-1while (low <= high) {const mid = Math.floor((low+high)/2)if (nums[mid] === target) return midif (nums[mid] < target) low = mid+1else high = mid-1}return -1
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function binarySearch(nums: T[], target: T): number {
let low = 0
let high = nums.length - 1
while (low <= high) {
const mid = low + Math.floor((high - low) / 2)
if (nums[mid] === target) return mid
if (nums[mid] < target) low = mid + 1
else high = mid - 1
}
return -1
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
Duy trì [low, high] là khoảng còn xét; mid = floor((low + high) / 2)
Nếu nums[mid] === target → trả về mid
Nếu nums[mid] < target → cắt nửa trái, low = mid + 1
Nếu nums[mid] > target → cắt nửa phải, high = mid - 1
Điều kiện while: low <= high (không phải <)
Tổng quát hoá — "nhị phân hoá trên đáp án": tìm giá trị nhỏ/lớn nhất thoả một predicate đơn điệu, không cần mảng sắp xếp sẵn
Lỗi thường gặp
Dùng while (low < high) thay vì low <= high → bỏ qua trường hợp mảng 1 phần tử
Tính mid = (low + high) / 2 có thể tràn số nguyên — viết low + (high - low) / 2 cho an toàn
Quên điều kiện mảng phải sắp xếp trước khi dùng tìm kiếm nhị phân
Độ phức tạp
Time O(log n), Space O(1)Bài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay