Ở bài trước các em đã được tìm hiểu về thuật toán tìm kiếm tuần tự trong bài hôm nay các em sẽ được tìm hiểu một loại thuật toán khác là thuật toán tìm kiếm nhị phân. Cùng DapAnHay tìm hiểu các kiến thức liên quan đến Thuật toán tìm kiếm nhị phân như: khái niệm, cách thực hiện, so sánh hai thuật toán tìm kiếm qua nội dung bài giảng của Bài 15: Thuật toán tìm kiếm nhị phân trong chương trình Tin học 7 Kết nối tri thức.
- Ví dụ: Việc kinh doanh mở rộng, số lượng khách hàng cùa cửa hàng bán giống cây trồng nhà An lên đến hàng trăm người. Việc tìm kiếm tên khách hàng trong danh sách thật khó khăn.
+ Khi danh sách khách hàng ngày càng nhiều, để thuận lợi cho việc tìm kiểm. An đã giúp mẹ soạn thảo danh sách khách hàng trên máy tính với tên khách hàng được sắp xếp theo thứ tự chữ cái. Giả sử An cần tìm địa chỉ của khách hàng tên là "Trúc" trong danh sách khách hàng như Hình 15.1.
Hình 15.1. Danh sách khách hàng
+ Khi danh sách đã được sắp xếp. An không cần tìm từ đầu mà so sánh ngay giá trị cần tìm với giá trị của vị trí ở giữa danh sách.
+ Nếu giá trị cần tìm bảng giá trị ở giữa thì tìm thấy và dừng lại, nếu lớn hơn thì chì cần tim ở nửa sau của danh sách, nếu nhỏ hơn thì tìm nửa đầu của danh sách.
+ Lặp lại quá trình đó cho đến khi tìm thấy hoặc hết danh sách.
Như vậy, tại mỗi bước lặp, thuật toán tìm kiếm thu hẹp danh sách tìm kiếm chỉ còn một nửa. Do đó thuật toán này có tên là tìm kiếm nhị phân (chia đôi).
- Các bước để An tìm khách hàng tên "Trúc" bằng thuật toán nhị phân
+ Bước 1. Xét vị trí ở giữa của dãy, đó là vị trí số 5
So sánh ‘Trúc" và "Mai".
Vì "T” đứng sau "M” trong bảng chữ cái nên bỏ đi nửa đầu danh sách.
+ Bước 2. Xét vị tri ở giữa của nửa sau của dãy là vị tri số 7
So sánh Trúc" và "Trang '.
Vì "Tru" đứng sau “Tra” trong bảng chữ cái nên bỏ đi nửa đầu danh sách.
+ Bước 3. Xét vị trí ở giữa của nửa sau còn lại của dãy, đó là vị trí số 8
So sánh “Trúc" và “Trúc”.
Vì hai giá trị bằng nhau nên thuật toán kết thúc.
Sau bước 3 đã tìm thấy tên khách hàng nên thuật toán kết thúc.
- Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên:
+ Bước 1. Nếu vùng tìm kiếm không có phần tử nào thì kết luận không tìm thấy và thuật toán kết thúc.
+ Bước 2. Xác định vị trí giữa của vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa
+ Bước 3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận “giá trị cần tìm xuất hiện tại vị trí giữa" và kết thúc.
+ Bước 4. Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn nửa trước của dãy. Ngược lại (nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa) vùng tìm kiếm mới được thu hẹp lại, chỉ còn nửa sau của dãy
+ Bước 5. Lặp lại từ Bước 1 đến Bước 4 cho đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc vùng tìm kiếm không còn phần tử nào (Bước 1).
Hình 15.2. Vùng tìm kiếm
* Lưu ý:
- Vị trí giữa của vùng tìm kiếm bằng phần nguyên của (vị trí đầu + vị trí cuối)/2
- Trong trường hợp so sánh kí tự thì kí tự đứng truớc lá "nhỏ hơn" kí tự đứng sau trong bảng chữ cái.
Thuật toán tìm kiếm nhị phân - Thực hiện trên danh sách đã được sắp xếp. Bắt đầu từ vị trí ở giữa danh sách. - Tại mỗi bước, so sánh giá trị cần tìm với giá trị của vị trí giữa danh sách, nếu lớn hơn thì tìm trong nửa sau của danh sách, nếu nhỏ hơn thì tìm trong nửa trước của danh sách, nếu bằng thì dừng lại. - Chừng nào chưa tìm thấy và chưa hết danh sách thì còn tìm tiếp. |
---|
- Ví dụ ở mục 1. khách hàng tên “Trúc" được tìm thấy sau 3 bước thực hiện theo thuật toán tìm kiếm nhị phân, trong khi thuật toán tìm kiếm tuần tự phải thực hiện 8 bước.
- Xét trưởng hợp có một khách hàng nào đó mà mẹ bạn An quên chưa ghi vào sổ, do đó tên khách hàng không có trong danh sách ở Hình 15.1. Khi phải tìm kiếm tên khách hàng này, thuật toán tìm kiếm tuần tự cần thực hiện 9 bước để xét hết danh sách và kết luận "Không tìm thấy", trong danh sách thuật toán tìm kiếm nhị phân chỉ mất 4 bước thực hiện.
⇒ Như vậy, trong ví dụ trên, thuật toán tìm kiếm nhị phân thực hiện tìm kiếm nhanh hơn thuật toán tìm kiếm tuần tự. Có được ưu điểm này là do trước khi thực hiện tìm kiếm nhị phân, danh sách khách hàng cần tìm đã được sắp xếp.
Sắp xếp giúp cho việc tìm kiếm được thực hiện nhanh hơn. |
---|
Bài tập 1: Tư tưởng của thuật toán tìm kiếm nhị phân là gì?
Hướng dẫn giải:
Tư tưởng của thuật toán tìm kiếm nhị phân là tại mỗi bước tiến hành so sánh X với phần tử giữa của dãy. Dựa vào bước so sánh này quyết định tìm kiếm ở nửa đầu hay ở nửa sau của danh sách.
Bài tập 2: Vị trí giữa của vùng tìm kiếm được tính như thế nào?
Hướng dẫn giải:
Dựa vào hình dưới đây để nêu cách tìm kiếm vị trí giữa
Vùng tìm kiếm
Vị trí giữa của vùng tìm kiếm là phần nguyên của (vị trị cuối + vị trí đầu)/2
Bài tập 3: Cho ví dụ về sử dụng thuật toán tìm kiếm nhị phân trong thực tế?
Hướng dẫn giải:
Ví dụ: Tìm một từ tiếng anh trong quyển từ điển. Vì các từ trong quyển từ điển đã được sắp xếp theo thứ tự nên sử dụng thuật toán tìm kiếm nhị phân sẽ phù hợp.
Qua bài học các em cần nắm được các về:
- Giải thích được thuật toán tìm kiếm nhị phân.
- Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên một bộ dữ liệu vào có kích thước nhỏ.
- Giải thích được mối liên quan giữa sắp xếp và tìm kiếm, nêu được ví dụ minh hoạ.
Các em có thể hệ thống lại nội dung kiến thức đã học được thông qua bài kiểm tra Trắc nghiệm Tin học 7 Kết nối tri thức Chủ đề 5 Bài 15 cực hay có đáp án và lời giải chi tiết.
Tư tưởng của thuật toán tìm kiếm nhị phân là gì?
Trong mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên thì tại bước “Xác định vị trí giữa của vùng tìm kiếm” là bước thứ mấy?
Trong thuật toán tìm kiếm nhị phân, sau khi thực hiện xong bước 1 mà chưa tìm thấy giá trị cần tìm thì vùng tìm kiếm sẽ là tìm vị trí nào?
Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!
Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 7 Kết nối tri thức Chủ đề 5 Bài 15để giúp các em nắm vững bài học và các phương pháp giải bài tập.
Khởi động trang 74 SGK Tin học 7 Kết nối tri thức - KNTT
Hoạt động 1 trang 75 SGK Tin học 7 Kết nối tri thức - KNTT
Câu hỏi trang 76 SGK Tin học 7 Kết nối tri thức - KNTT
Câu hỏi trang 77 SGK Tin học 7 Kết nối tri thức - KNTT
Luyện tập 1 trang 77 SGK Tin học 7 Kết nối tri thức - KNTT
Luyện tập 2 trang 77 SGK Tin học 7 Kết nối tri thức - KNTT
Vận dụng trang 77 SGK Tin học 7 Kết nối tri thức - KNTT
Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học DapAnHay sẽ hỗ trợ cho các em một cách nhanh chóng!
Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!
-- Mod Tin Học 7 DapAnHay
Tư tưởng của thuật toán tìm kiếm nhị phân là gì?
Trong mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên thì tại bước “Xác định vị trí giữa của vùng tìm kiếm” là bước thứ mấy?
Trong thuật toán tìm kiếm nhị phân, sau khi thực hiện xong bước 1 mà chưa tìm thấy giá trị cần tìm thì vùng tìm kiếm sẽ là tìm vị trí nào?
Vị trí giữa của vùng tìm kiếm được tính như thế nào?
Khi so sánh giá trị cần tìm với giá trị của vị trí giữa, nếu giá trị cần tìm nhỏ hơn giá trị giữa thì ta tìm vị trí nào?
Sử dụng thuật toán tìm kiếm nhị phân sẽ phù hợp trong trường hợp nào dưới đây?
Trong mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên thì tại bước “Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận giá trị cần tìm xuất hiện tại vị trí giữa và kết thúc” là bước thứ mấy?
Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên gồm có mấy bước?
Điều kiện dừng trong thuật toán tìm kiếm nhị phân là gì?
Thuật toán tìm kiếm nhị phân bắt đầu thực hiện ở vị trí nào trong danh sách?
Việc kinh doanh mở rộng, số lượng khách hàng của cửa hàng bán giống cây trồng nhà An lên đến hàng trăm người. Việc tìm kiếm tên khách hàng trong danh sách thật khó khăn. Em có gợi ý gì cho bạn An để việc tìm kiếm được dễ dàng hơn không?
1. Em hãy cho biết thuật toán tìm kiếm tuần tự phải thực hiện bao nhiêu bước để tìm được khách hàng tên “Trúc” trong danh sách ở Hình 15.1? Em hãy so sánh số bước thực hiện của thuật toán tìm kiếm tuần tự với số bước thực hiện của thuật toán tìm kiếm nhị phân.
2. Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thoả mãn điều kiện gì? Nếu không thoả mãn điều kiện đó, thuật toán tìm kiếm nhị phân có thực hiện được không?
Em hãy viết các bước thực hiện thuật toán tìm kiếm nhị phân để tìm khách hàng tên “Hoà” trong danh sách ở Hình 15.1
Em hãy nêu ví dụ trong thực tế cho thấy mối liên quan giữa sắp xếp và tìm kiếm.
Cho danh sách tên các nước sau đây:
Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greenland, Germany
a) Em hãy sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái.
b) Em hãy liệt kê các bước tìm kiếm tên nước Iceland trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân.
c) Em hãy so sánh số bước thực hiện tìm kiếm ở phần b với số bước thực hiện tìm kiếm ở Câu 2 phần Luyện tập của bài 14.
Em hãy cho ví dụ một bài toán tìm kiếm trong thực tế mà có thể thực hiện bằng thuật toán tìm kiếm nhị phân? Hãy thực hiện thuật toán tìm kiếm nhị phân để giải quyết bài toán đó.
Em tìm một từ tiếng Anh trong quyển từ điển theo cách nào? Tại sao em lại dùng cách đó?
Trả lời:
Em tìm một từ tiếng Anh trong quyển từ điển theo cách tìm kiếm nhị phân.
Giả sử cuốn từ điển có khoảng 300 nghìn mục từ. Nếu tìm kiếm tuần tự thì mất rất nhiều thời gian. Nếu tra một từ trong từ điển bằng cách tìm kiếm nhị phân thì sau một lần chia đôi, phạm vi tìm kiếm giảm đi.
Họ và tên
Tiêu đề câu hỏi
Nội dung câu hỏi
0 Bình luận
Để lại bình luận
Địa chỉ email của hạn sẽ không được công bố. Các trường bắt buộc được đánh dấu *