1. Kiến thức trọng tâm
Tìm kiếm nhị phân là cách tìm một giá trị trong danh sách đã được sắp xếp bằng cách liên tục thu hẹp phạm vi tìm kiếm. Mỗi bước, ta xét phần tử ở giữa đoạn đang tìm và so sánh với giá trị cần tìm, rồi loại bỏ một nửa đoạn không chứa giá trị đó.
Các bước của thuật toán: xác định đoạn tìm kiếm từ đầu đến cuối danh sách. Tìm phần tử ở giữa đoạn. Nếu phần tử giữa bằng giá trị cần tìm thì dừng lại. Nếu giá trị cần tìm nhỏ hơn phần tử giữa, tiếp tục tìm ở nửa bên trái. Nếu lớn hơn, tiếp tục tìm ở nửa bên phải. Lặp lại cho đến khi tìm thấy hoặc đoạn tìm kiếm không còn phần tử nào.
Điều kiện quan trọng: danh sách phải được sắp xếp trước. Nhờ loại bỏ một nửa mỗi lần, tìm kiếm nhị phân nhanh hơn nhiều so với tìm kiếm tuần tự khi danh sách dài.
2. Ví dụ minh họa
Tìm số 7 trong danh sách đã sắp xếp: 1, 3, 5, 7, 9, 11, 13.
- Đoạn tìm kiếm là cả danh sách, phần tử giữa là 7.
- So sánh: 7 bằng giá trị cần tìm nên dừng lại ngay.
- Kết luận: số 7 ở vị trí thứ tư.
Tìm số 11 trong cùng danh sách:
- Phần tử giữa là 7, nhỏ hơn 11 nên tìm ở nửa phải: 9, 11, 13.
- Phần tử giữa của nửa phải là 11, bằng giá trị cần tìm nên dừng lại.
- Kết luận: số 11 ở vị trí thứ sáu.
3. Ghi nhớ
- Tìm kiếm nhị phân chỉ áp dụng cho danh sách đã sắp xếp.
- Mỗi bước loại bỏ một nửa đoạn tìm kiếm.
- Nhanh hơn tìm kiếm tuần tự khi danh sách dài.
- Nếu đoạn tìm kiếm rỗng, kết luận giá trị không có trong danh sách.