Tổng quan
Binary Search (tìm kiếm nhị phân) là thuật toán chia-để-trị nhanh dành cho mảng đã sắp xếp. Nó liên tục so sánh mục tiêu với phần tử ở giữa và loại bỏ nửa không thể chứa nó, giảm một nửa không gian tìm kiếm sau mỗi bước.
Vì mỗi phép so sánh loại bỏ một nửa số ứng viên còn lại, Binary Search tìm ra đáp án trong số bước logarit — nhanh hơn hẳn so với việc quét từng phần tử trên dữ liệu lớn.
Tìm kiếm nhị phân hoạt động thế nào?
- Đặt hai biên low và high tại chỉ số đầu và cuối của mảng đã sắp xếp.
- Tính chỉ số giữa và so sánh phần tử tại đó với mục tiêu.
- Nếu khớp, trả về chỉ số đó; việc tìm kiếm kết thúc.
- Nếu mục tiêu nhỏ hơn, chuyển high xuống ngay dưới điểm giữa; nếu lớn hơn, chuyển low lên ngay trên điểm giữa.
- Lặp lại khi low ≤ high; nếu hai biên vượt qua nhau, mục tiêu không tồn tại.
Khi nào nên dùng?
- Tra cứu lặp lại trong mảng lớn đã sắp xếp, khi chi phí O(log n) được hoàn vốn nhiều lần.
- Tìm vị trí chèn hoặc biên (lower/upper bound) trong dữ liệu có thứ tự.
- Làm khối xây dựng cho truy vấn khoảng và các thuật toán tìm kiếm khác trên mảng đã sắp xếp.
Phân tích độ phức tạp
Nhờ giảm một nửa khoảng ở mỗi bước, Binary Search chạy trong thời gian O(log n) ở trường hợp trung bình và xấu nhất, với trường hợp tốt nhất O(1) khi phần tử giữa chính là mục tiêu. Nó dùng O(1) bộ nhớ phụ khi cài đặt lặp. Điều kiện tiên quyết then chốt là mảng phải được sắp xếp.
Câu hỏi thường gặp
Vì sao mảng phải được sắp xếp để dùng Binary Search?
Thuật toán quyết định loại bỏ nửa nào bằng cách so sánh với phần tử giữa. Quyết định đó chỉ đúng nếu thứ tự đảm bảo mọi phần tử một bên đều nhỏ hơn và mọi phần tử bên kia đều lớn hơn.
Binary Search nhanh hơn Linear Search bao nhiêu?
Với một triệu phần tử, Linear Search có thể cần tới một triệu phép so sánh trong khi Binary Search chỉ cần khoảng hai mươi (log₂ của một triệu). Khoảng cách này càng lớn khi mảng càng to.