Chúng ta đã biết thuật toán tìm kiếm nhị phân trên các dãy phần tử đã sắp xếp. Hãy tìm tới thiết kế mới của thuật toán này theo kĩ thuật đệ quy. Trao đổi, thảo luận và trả lời các câu hỏi sau:
1. Nêu ý tưởng chính của giải thuật tìm kiếm nhị phân sử dụng đệ quy
2. Vị trí nào trong thuật toán có thể gợi ý cho kĩ thuật đệ quy?
3. Phần cơ sở của thiết kế đệ quy nằm ở bước nào?
Bằng cách nhấp vào Đăng nhập, bạn đồng ý Chính sách bảo mật và Điều khoản sử dụng của chúng tôi. Nếu đây không phải máy tính của bạn, để đảm bảo an toàn, hãy sử dụng Cửa sổ riêng tư (Tab ẩn danh) để đăng nhập (New Private Window / New Incognito Window).
1. Ý tưởng chính của giải thuật tìm kiếm nhị phân sử dụng đệ quy là phân chia dãy phần tử đã sắp xếp thành hai nửa bằng nhau, tìm kiếm phần tử cần tìm trong nửa phù hợp và tiếp tục phân chia và tìm kiếm đệ quy cho đến khi tìm thấy phần tử hoặc không tìm thấy.
2. Vị trí trong thuật toán có thể gợi ý cho kĩ thuật đệ quy là phần phân chia dãy phần tử thành hai nửa bằng nhau, tìm kiếm trong nửa phù hợp và tiếp tục phân chia và tìm kiếm đệ quy cho đến khi tìm thấy phần tử hoặc không tìm thấy. Đây là một bài toán con nhỏ hơn của bài toán ban đầu và có thể được giải quyết bằng cùng một thuật toán đệ quy.
3. Phần cơ sở của thiết kế đệ quy nằm ở bước cuối cùng của thuật toán, khi không còn cách nào để phân chia dãy phần tử nữa và ta chỉ còn lại một phần tử hoặc không có phần tử nào để tìm kiếm. Khi đó, ta kết luận bài toán đệ quy đã được giải quyết và trả về kết quả.
Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi
Vui | Buồn | Bình thường |