1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự
2. Thuật toán tìm kiếm nhị phân
- Tìm kiếm nhị phân là tìm kiếm bằng cách chia dãy làm hai nửa, loại bỏ nửa dãy chắc chắn không chứa phần tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại.
- Khi dãy có thứ tự thì mới áp dụng được tìm kiếm nhị phân.
- Thuật toán tìm kiếm nhị phân (tìm x trong dãy số đã sắp thứ tự không giảm)
Bước 1. Phạm vi tìm kiếm là dãy ban đầu, kết quả = Chưa tìm thấy.
Bước 2. Lặp khi (Phạm vi tìm kiếm dài hơn 1) và (kết quả = Chưa tìm thấy):
a) Xác định phần từ giữa Phạm vi tìm kiếm, gọi là am.
b) Nếu x = am kết quả = Tìm thấy. Thông báo tìm thấy x ở vị trí m;
Trái lại:
Loại bỏ nửa dãy chắc chắn không chứa x;
Phạm vi tìm kiếm = nửa dãy còn lại;
Hết nhánh
Hết lặp.
Bước 3. Nếu (Phạm vi tìm kiếm chỉ còn một số ai) và (x = ai):
Kết quả = Tìm thấy: Thông báo tìm thấy x ở vị trí k;
Hết nhánh.
Bước 4. Nếu kết quả = Chưa tìm thấy: Thông báo không có x trong dãy;
Hết nhánh.
3. Chiến lược “chia để trị" với bài toán tìm kiếm
Thuật toán tìm kiếm nhị phân chia bài toán ban đầu thành hai bài toán con nhỏ hơn và chỉ phải tiếp tục giải một trong hai bài toán con đó. Áp dụng liên tiếp cách làm này cho đến khi nhận được kết quả.