1. Em hãy cho biết thuật toán tìm kiếm tuần tự phải thực hiện bao nhiêu bước để tìm khách hàng tên Trúc như ở Hình 15.1? Em hãy so sánh số bước thực hiện của thuật toán tìm kiếm tuần tự với số bước thực hiện thuật toán tìm kiếm nhị phân.
2. Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thỏa mãn điều kiện gì? Nếu không thỏa mãn điều kiện đó, thuật toán tìm kiếm nhị phân có thực hiện được không?
- Quan sát Hình 15.1
- Thuật toán tìm kiếm tuần tự: tìm kiếm lần lượt từ đầu danh sách cho đến khi tìm được
- Thuật toán tìm kiếm nhị phân: so sánh giá trị ở giữa danh sách đã được sắp xếp với giá trị cần tìm.
Advertisements (Quảng cáo)
1. Thuật toán tìm kiếm tuần tự phải thực hiện 3 bước để tìm khách hàng tên Trúc như ở Hình 15.1.
- Số bước thực hiện của thuật toán tìm kiếm tuần tự nhiều hơn so với số bước thực hiện thuật toán tìm kiếm nhị phân vì thuật toán tìm kiếm tuần tự sẽ tìm kiếm lần lượt từ đầu danh sách cho đến khi tìm được tên của bạn Trúc nên sẽ mất 8 lần lặp, còn thuật toán tìm kiếm nhị phân so sánh giá trị ở giữa danh sách nên sẽ nhanh chóng hơn.
2. Trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần phải được sắp xếp theo quy tắc (theo bảng chữ cái, số thứ tự tăng dần hoặc giảm dần).
Nếu không thỏa mãn điều kiện đó, thuật toán tìm kiếm nhị phân không thực hiện được.