Lý thuyết Tin học 7 Cánh diều Bài 2: Tìm kiếm nhị phân
Với tóm tắt lý thuyết Tin học lớp 7 Bài 2: Tìm kiếm nhị phân sách Cánh diều hay nhất, ngắn gọn sẽ giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt môn Tin học 7.
Lý thuyết Tin học 7 Cánh diều Bài 2: Tìm kiếm nhị phân
Chỉ từ 100k mua trọn bộ lý thuyết Tin 7 Cánh diều (cả năm) bản word trình bày đẹp mắt, dễ dàng chỉnh sửa:
- B1: gửi phí vào tk:
0711000255837
- NGUYEN THANH TUYEN - Ngân hàng Vietcombank (QR) - B2: Nhắn tin tới Zalo VietJack Official - nhấn vào đây để thông báo và nhận giáo án
1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự
Ví dụ: Tìm x = 44 trong dãy 8 phần tử đã xếp thứ tự không giảm 6, 12, 18, 42, 44, 55, 67, 94. Bảng dưới minh hoạ từng bước chia đôi dần để tìm kiếm.
Hình 1: Bước tìm kiếm nhị phân
- Chia đôi lần 1: Phạm vi tìm kiếm là dãy a1 đến a8. Lấy a4 là số có vị trí giữa dãy. Vì x>a4 là nửa đầu dãi chắc chắn không chứa x = 44, sau đó ta thu hẹp vị trí tìm kiếm.
- Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a5 đến a8. Lấy a6 là số có vị trí giữa dãy. Vì x < a6 nên nửa sau không chưa x = 44. Tiếp theo ta chỉ cần tìm trong nửa đầu của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con chỉ còn một số a5.
- Kết thúc thuật toán với kết quả. Tìm thấy x ở vị trí thứ năm.
2. Thuật toán tìm kiếm nhị phân
- Tìm kiếm nhị phân là tìm kiếm bằng cách chia dãy làm hai nửa, loại bỏ nửa dãy chắc chắn không chứa phần tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại.
- Khi dãy có thứ tự thì mới áp dụng được tìm kiếm nhị phân.
- Thuật toán tìm kiếm nhị phân (tìm x trong dãy số đã sắp thứ tự không giảm)
Bước 1. Phạm vi tìm kiếm là dãy ban đầu, kết quả = Chưa tìm thấy.
Bước 2. Lặp khi (Phạm vi tìm kiếm dài hơn 1) và (kết quả = Chưa tìm thấy):
a) Xác định phần từ giữa Phạm vi tìm kiếm, gọi là am.
b) Nếu x = am kết quả = Tìm thấy. Thông báo tìm thấy x ở vị trí m;
Trái lại:
Loại bỏ nửa dãy chắc chắn không chứa x;
Phạm vi tìm kiếm = nửa dãy còn lại;
Hết nhánh
Hết lặp.
Bước 3. Nếu (Phạm vi tìm kiếm chỉ còn một số ai) và (x = ai):
Kết quả = Tìm thấy: Thông báo tìm thấy x ở vị trí k;
Hết nhánh.
Bước 4. Nếu kết quả = Chưa tìm thấy: Thông báo không có x trong dãy;
Hết nhánh.
3. Chiến lược “chia để trị" với bài toán tìm kiếm
Thuật toán tìm kiếm nhị phân chia bài toán ban đầu thành hai bài toán con nhỏ hơn và chỉ phải tiếp tục giải một trong hai bài toán con đó. Áp dụng liên tiếp cách làm này cho đến khi nhận được kết quả.
Xem thêm tóm tắt lý thuyết Tin học lớp 7 Cánh diều hay khác:
Lý thuyết Tin học 7 Bài 15: Thực hành tổng hợp tạo bài trình chiếu
Lý thuyết Tin học 7 Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp
Tủ sách VIETJACK shopee lớp 6-8 cho phụ huynh và giáo viên (cả 3 bộ sách):
Săn shopee giá ưu đãi :
- Sổ lò xo Art of Nature Thiên Long màu xinh xỉu
- Biti's ra mẫu mới xinh lắm
- Tsubaki 199k/3 chai
- L'Oreal mua 1 tặng 3
Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.
Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:Loạt bài Giải bài tập Tin học lớp 7 của chúng tôi được biên soạn bám sát nội dung sgk Tin học lớp 7 Cánh diều (NXB Đại học Sư phạm).
Nếu thấy hay, hãy động viên và chia sẻ nhé! Các bình luận không phù hợp với nội quy bình luận trang web sẽ bị cấm bình luận vĩnh viễn.
- Soạn văn 7 (hay nhất) - Cánh diều
- Soạn văn 7 (ngắn nhất) - Cánh diều
- Giải sgk Toán 7 - Cánh diều
- Giải Tiếng Anh 7 Global Success
- Giải Tiếng Anh 7 Friends plus
- Giải sgk Tiếng Anh 7 Smart World
- Giải Tiếng Anh 7 Explore English
- Giải sgk Khoa học tự nhiên 7 - Cánh diều
- Giải sgk Lịch Sử 7 - Cánh diều
- Giải sgk Địa Lí 7 - Cánh diều
- Giải sgk Giáo dục công dân 7 - Cánh diều
- Giải sgk Công nghệ 7 - Cánh diều
- Giải sgk Tin học 7 - Cánh diều
- Giải sgk Hoạt động trải nghiệm 7 - Cánh diều
- Giải sgk Âm nhạc 7 - Cánh diều