1. Kiến thức trọng tâm
Bài toán tìm kiếm là một trong những bài toán cơ bản nhất của tin học. Nội dung bài toán: cho một dãy phần tử và một giá trị cần tìm, hãy xác định giá trị đó có xuất hiện trong dãy hay không và nằm ở vị trí nào. Bài toán này gặp nhiều trong thực tế, như tra cứu tên học sinh trong danh sách lớp hay tìm sách trong thư viện.
Hai thuật toán tìm kiếm cơ bản là tìm kiếm tuần tự và tìm kiếm nhị phân. Tìm kiếm tuần tự duyệt lần lượt từng phần tử, so sánh với giá trị cần tìm đến khi gặp phần tử bằng nó hoặc duyệt hết dãy. Thuật toán này đơn giản, dễ cài đặt và áp dụng được với mọi dãy, kể cả dãy chưa sắp xếp.
Tìm kiếm nhị phân áp dụng cho dãy đã sắp xếp. Thuật toán so sánh giá trị cần tìm với phần tử giữa dãy: nếu bằng thì dừng; nếu nhỏ hơn thì tìm tiếp ở nửa trái; nếu lớn hơn thì tìm tiếp ở nửa phải, lặp lại đến khi tìm thấy hoặc hết khoảng tìm kiếm.
2. Ví dụ minh họa
Ví dụ: cho dãy đã sắp xếp tăng dần 2, 5, 9, 14, 21, 30, cần tìm giá trị 14. Áp dụng tìm kiếm nhị phân: phần tử giữa dãy là 9. Vì 14 > 9, chỉ xét nửa phải 14, 21, 30. Phần tử giữa nửa phải là 21. Vì 14 < 21, chỉ xét nửa trái của nửa phải, còn 14. So sánh cho thấy 14 = 14, vậy tìm thấy giá trị tại vị trí thứ tư. Thuật toán chỉ cần ba lần so sánh, ít hơn tìm kiếm tuần tự.
3. Ghi nhớ
- Bài toán tìm kiếm: xác định giá trị cần tìm có trong dãy hay không và ở vị trí nào.
- Tìm kiếm tuần tự: duyệt lần lượt từng phần tử, áp dụng được với mọi dãy.
- Tìm kiếm nhị phân: chỉ áp dụng với dãy đã sắp xếp, nhanh hơn khi dãy dài.
- Chọn thuật toán tùy thuộc dãy đã sắp xếp hay chưa.