Hãy mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân?
Câu 1 trang 83 Tin học lớp 7: Hãy mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân?
Mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân:
Khi bắt đầu thuật toán, phạm vi tìm kiếm là dãy đã cho ban đầu. Lấy phần tử đứng giữa để so sánh với x.
+ Nếu phần tử đó chính là x thì kết luận. Đã tìm thấy x và kết thúc thuật toán.
+ Trái lại, ta có thể xác định được x chắc chắn không có trong nửa đầu hay nửa sau của dãy, từ đó xác định được phạm vi tìm kiếm ở bước tiếp theo là nửa còn lại.
Tiếp theo, việc tìm x trong phạm vi tìm kiếm (tức là nửa dãy còn lại) sẽ được lặp lại cho cho đến khi tìm thấy hoặc độ dài cần tìm chỉ còn bằng 1 và so sánh được ngay để biết tìm thấy x hay không.
Xem thêm lời giải bài tập Tin học lớp 7 Cánh diều hay, chi tiết khác: