Thuật toán
Mô phỏng thuật toán tìm kiếm nhi phân
09
thg 5
thg 5
MÔ PHỎNG THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Tình huống mở đầu (gợi ý vấn đề):
Thầy đang nghĩ đến một con số có giá trị nằm trong khoảng từ 1 đến 100. Em chỉ được hỏi: Số đó lớn hơn, nhỏ hơn hay bằng số mà em đoán? Làm sao để đoán số đó nhanh nhất?"
=> HS thường đoán đại, sau đó có em đề xuất: "Chia đôi khoảng để đoán!"
Bước 1: Trò chơi nhóm – Đoán số bí mật - Lớp chia thành 4 nhóm. Mỗi nhóm chọn một bạn làm “người giữ số bí mật” (ví dụ: số bất kỳ từ 1 đến 100, không cho các bạn còn lại biết).
- Các bạn còn lại trong nhóm phải tìm ra số đó bằng cách đoán và nhận phản hồi lớn hơn/ nhỏ hơn / đúng.
- Nhóm nào tìm được số đó ít lần đoán nhất là nhóm thắng.
- Giới hạn mỗi lượt đoán: 7 lần
Bước 2: Rút ra quy luật
Gợi ý học sinh thảo luận:- Tại sao nhóm A chỉ mất 6 lượt mà nhóm B mất đến 12 lượt?
- Nhóm A có dùng chiến thuật gì đặc biệt không?
- HS nhận ra: nếu mỗi lần chia đôi khoảng tìm kiếm thì sẽ nhanh hơn.
Bước 3: Khám phá bằng mô phỏng
- GV sử dụng mô phỏng
- Danh sách số đã sắp xếp.
- Cho học sinh quan sát từng bước tìm kiếm nhị phân hoạt động như thế nào khi tìm số.
Mô phỏng Tìm kiếm Nhị phân
Tốc độ: (ms)
Thuật toán tìm kiếm nhị phân:
B1. Đặt left = 0, right = độ dài mảng - 1
B2. Lặp lại khi left <= right:
- mid = (left + right) // 2
- Nếu arr[mid] == target → Tìm thấy
- Nếu arr[mid] < target → Cập nhật left = mid + 1
- Nếu arr[mid] > target → Cập nhật right = mid - 1
B3. Nếu thoát vòng lặp mà chưa tìm thấy → Không tồn tại
