Bài 22. Thuật toán tìm kiếm nhị phân
Bài học giới thiệu tìm kiếm nhị phân - thuật toán tìm kiếm nhanh hơn tìm kiếm tuần tự rất nhiều khi áp dụng trên một dãy dữ liệu đã được sắp xếp - cùng cách cài đặt bằng Python.
- Kết nối tri thứcTin học 11 (Khoa học máy tính) - Bài 20. Thực hành bài toán tìm kiếmtr. 94–98
Bắt đầu bằng một hình dung
Hãy tưởng tượng bạn chơi một trò đoán số quen thuộc: một người nghĩ trong đầu một số bất kỳ từ 1 đến 100, còn bạn phải đoán ra số đó trong ít lần nhất có thể. Sau mỗi lần đoán, người kia chỉ cho bạn biết số cần tìm cao hơn hay thấp hơn số bạn vừa đoán, chứ không nói thẳng đáp án.
Nếu đoán bừa từ 1, 2, 3... bạn có thể phải đoán tới gần 100 lần mới ra. Nhưng nếu chọn cách thông minh hơn, bạn sẽ đoán ngay con số nằm ở giữa khoảng còn có thể đúng. Giả sử số bí mật là 73: bạn đoán 50, được báo “cao hơn”, nghĩa là số cần tìm chỉ có thể nằm trong khoảng từ 51 đến 100. Bạn đoán tiếp số ở giữa khoảng đó là 75, được báo “thấp hơn”, khoảng còn nghi ngờ thu hẹp về 51 đến 74. Cứ mỗi lần đoán vào giữa khoảng còn lại như vậy, khoảng đó lại co xuống còn một nửa, nên chỉ sau khoảng 6–7 lần, bạn chắc chắn tìm ra đúng số cần tìm trong cả trăm số.
Cách làm này gần giống việc bạn tra một từ trong cuốn từ điển giấy dày cả nghìn trang: thay vì lật từng trang từ đầu, bạn mở đại vào khoảng giữa cuốn sách, so sánh từ đang mở với từ cần tìm theo thứ tự bảng chữ cái, rồi quyết định lật tiếp về nửa trước hay nửa sau. Cách “luôn nhìn vào giữa rồi thu hẹp dần” đó chính là ý tưởng cốt lõi của thuật toán tìm kiếm nhị phân - cách máy tính tìm kiếm rất nhanh trong một dãy dữ liệu đã được sắp xếp.
Nội dung bài học
- Điều kiện tiên quyết: dãy phải được sắp xếp
- Ý tưởng: nhìn vào giữa rồi thu hẹp dần
- Vì sao tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự rất nhiều
Tóm tắt lý thuyết cần nhớ
- Tìm kiếm nhị phân chỉ cho kết quả đúng khi dãy dữ liệu đã được sắp xếp (tăng dần hoặc giảm dần).
- Ý tưởng: so sánh giá trị ở vị trí giữa đoạn đang xét với x; nếu chưa đúng thì thu hẹp về nửa trái hoặc nửa phải, lặp lại đến khi tìm thấy hoặc đoạn xét rỗng.
- Cài đặt bằng vòng
whilevới ba biếntrai,phai,giua, trong đógiua = (trai + phai) // 2được tính lại sau mỗi bước. - Vì mỗi bước loại bỏ một nửa số phần tử đang xét, tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự rất nhiều khi dãy có kích thước lớn.
Thuật ngữ tiếng Anh trong bài
| Tiếng Anh | Đọc là | Nghĩa |
|---|---|---|
| search | XƠ-chờ | tìm kiếm Đi tìm xem một phần tử có trong dãy hay không - giống tìm một cuốn sách trên giá sách đầy ắp. |
| list | lít | danh sách Một dãy nhiều giá trị xếp hàng, giống hộp bút có nhiều ô. |
Câu hỏi trắc nghiệm có đáp án
Mấy câu mẫu để bạn tự kiểm tra ngay. Trong ứng dụng, bài này có đủ 26 câu, chấm điểm tự động và giải thích từng câu sai.
- Dãy có ít hơn 10 phần tử để mỗi lần chia đôi đều chia được trọn vẹn
- Dãy đã được sắp xếp theo thứ tự (tăng dần hoặc giảm dần)
- Dãy chỉ chứa số nguyên dương, không có số âm hay số thập phân
- Dãy không được chứa phần tử trùng nhau để khỏi tìm nhầm vị trí
- Dừng lại ngay và kết luận không tìm thấy x
- Chuyển phai xuống giua - 1 để tìm ở nửa bên trái
- Chuyển trai lên giua + 1 để tìm ở nửa bên phải
- Bắt đầu lại toàn bộ dãy từ đầu
- Chỉ số 3, giá trị 9
- Chỉ số 4, giá trị 12
- Chỉ số 3, giá trị 12
- Chỉ số 6, giá trị 20
- a)Tìm kiếm nhị phân có thể áp dụng cho một dãy bất kỳ, kể cả khi dãy chưa được sắp xếp.Sai
- b)Ở mỗi bước, nếu giá trị tại vị trí giua bằng đúng giá trị x cần tìm, thuật toán dừng lại ngay và trả về vị trí đó.Đúng
- c)Với dãy có kích thước rất lớn, tìm kiếm nhị phân thường cần ít bước so sánh hơn nhiều so với tìm kiếm tuần tự.Đúng
- d)Biến giua luôn được tính bằng trai cộng phai, không cần chia đôi.Sai
- (a) Sai - dãy bắt buộc phải được sắp xếp trước thì tìm kiếm nhị phân mới cho kết quả đúng.
- (b) Đúng - khi giá trị tại giua trùng với x, thuật toán tìm thấy ngay và dừng lại.
- (c) Đúng - mỗi bước loại bỏ một nửa số phần tử nên số bước cần thiết tăng rất chậm dù dãy lớn đến đâu.
- (d) Sai - phải chia đôi: giua = (trai + phai) // 2; nếu không chia đôi thì giua sẽ vượt ra ngoài phạm vi dãy.
Thử ngay: minh hoạ từng bước
Bấm từng bước để tự xem cơ chế hoạt động, hoặc bấm “Tự chạy” cho nó tiến mỗi giây một lần. Đổi được dữ liệu đầu vào - không cần đăng nhập.
Học trọn bài này trong ứng dụng
Bài giảng đầy đủ, 26 câu luyện tập chấm tự động, thi thử đúng cấu trúc đề tốt nghiệp (24 trắc nghiệm + 4 Đúng/Sai), bài thực hành máy tự chấm và gia sư AI giải thích chỗ sai.
Phần học miễn phí, không cần tạo tài khoản.
Bài liên quan - Lập trình, Thuật toán & CTDL (KHMT)
Cùng mạch kiến thức với bài này, học nối tiếp cho chắc phần lí thuyết.