Tìm kiếm tuần tự và tìm kiếm nhị phân – đếm số lần so sánh

Học sinh lớp 7 học thuật toán tìm kiếm tuần tự và tìm kiếm nhị phân trong chủ đề Giải quyết vấn đề với sự trợ giúp của máy tính. Mục tiêu là so sánh hai thuật toán qua số lần so sánh. Trên cùng một dãy 5–20 phần tử, hai thuật toán có thể chạy song song. Tìm kiếm tuần tự duyệt từ đầu dãy; tìm kiếm nhị phân so với phần tử giữa rồi loại bỏ một nửa phạm vi. Bấm Từng bước để thấy ô đang so sánh, vùng bị loại và bộ đếm của mỗi bên; bấm vào một ô để đổi giá trị cần tìm. Tắt “Dãy đã sắp xếp tăng dần” sẽ thấy tìm kiếm nhị phân không dùng được, sửa quan niệm sai rằng nó luôn tốt hơn. Với dãy dài, số lần so sánh của tìm kiếm nhị phân ít hơn hẳn. Câu hỏi gợi ý: – Dãy 16 phần tử cần tối đa bao nhiêu lần so sánh khi tìm nhị phân? – Khi nào tìm kiếm tuần tự lại nhanh hơn? – Vì sao tìm kiếm nhị phân cần dãy đã sắp xếp?