Ở bài học trước các em đã được tìm hiểu về thuật toán tìm kiếm tuần tự, bài học hôm nay các em sẽ được tìm hiểu một thuật toán tìm kiếm khác là tìm kiếm nhị phân. Hai thuật toán này khác nhau như thế nào? Mời các em cùng tham khảo nội dung bài giảng của Bài 2: Tìm kiếm nhị phân của chủ đề F trong chương trình Tin học 7 Cánh diều do DapAnHay tổng hợp và biên soạn dưới đây!
- Ý tưởng: chia đôi dần để tìm một số trong một dãy số
- 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 họa từng bước chia đôi dần để tìm kiếm.
- Minh họa các bước:
- Mô phỏng thuật toán tìm kiếm nhị phân
+ Lượt thứ nhất: agiữa là a4 = 42; 42 < 44 = x
→ vùng tìm kiếm thu hẹp trong phạm vi từ a5 → a8;
+ Lượt thứ hai: agiữa là a6 = 55; 55 > 44
→ vùng tìm kiếm thu hẹp trong phạm vi là a5
+ Lượt thứ ba: agiữa là a5 = 44; 44 = 44 = x
→ Vậy số cần tìm là i = 5.
- Thuật toán tìm kiếm nhị phân là thuật toán tìm kiếm x trong dãy đã sắp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm.
- Ý tưởng: Chia đôi dần để giảm nhanh phạm vi tìm kiếm.
- Mô tả thuật toán:
Một mô tả của thuật toá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 dãy là am để so sánh với x. Nếu am = x thì kết thúc. Trái lại, sẽ có hai trường hợp:
+ Nếu am < x thì chắc chắn không có x trong nửa đầu của dãy.
+ Nếu x < am thì chắc chắn không có x trong nửa sau của dãy.
→ Lặp lại theo cách như thế cho đến khi hoặc tìm thấy hoặc độ dài dãy phạm vi tìm kiếm là bằng 0.
- Để giải một bài toán lớn, người ta tìm cách chia bài toán ban đầu ra thành các bài toán nhỏ hơn rồi giải những bài toán nhỏ hơn sẽ dễ hơn. Cách làm này gọi là “chia để trị”
- 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 đó, cho đến đi nhận được kết quả.
- 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. |
---|
Bài tập 1: Tìm kiếm nhị phân là gì?
Hướng dẫn giải:
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.
Bài tập 2: Vì sao tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự?
Hướng dẫn giải:
Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì: Dãy đã được sắp xếp và 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.
Bài tập 3: Điều kiện để áp dụng thuật toán nhị phân là gì?
Hướng dẫn giải:
Điều kiện để áp dụng thuật toán nhị phân là dãy đã được sắp xếp tăng dần hoặc giảm dần.
Qua bài học các em có thể:
- Mô phỏng được hoạt độn của thuật toán tìm kiếm nhị phân trên một bộ dữ liệu đầu vào có kích thước nhỏ
- Biết được tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự
- Nêu được ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn
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 Cánh diều Chủ đề F Bài 2 cực hay có đáp án và lời giải chi tiết.
Tìm kiếm nhị phân là gì?
Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì sao?
Bài toán nào sau đây áp dụng được thuật toán tìm kiếm nhị phân?
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 Cánh diều Chủ đề F Bài 2để 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 81 SGK Tin học 7 Cánh diều - CD
Hoạt động trang 81 SGK Tin học 7 Cánh diều - CD
Luyện tập trang 83 SGK Tin học 7 Cánh diều - CD
Vận dụng trang 83 SGK Tin học 7 Cánh diều - CD
Câu hỏi tự kiểm tra 1 trang 83 SGK Tin học 7 Cánh diều - CD
Câu hỏi tự kiểm tra 2 trang 83 SGK Tin học 7 Cánh diều - CD
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ìm kiếm nhị phân là gì?
Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì sao?
Bài toán nào sau đây áp dụng được thuật toán tìm kiếm nhị phân?
Cho dãy số 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy” có phạm vi tìm kiếm là ở khoảng nào?
Thuật toán tìm kiếm x trong dãy đã sắp xếp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm được gọi là gì?
Tìm kiếm nhị phân và tìm kiếm tuần tự thì thuật toán nào nhanh hơn?
Thuật toán tìm kiếm nhị phân được sử dụng khi nào?
Trong bài toán tìm kiếm nhị phân đối với dãy đã sắp xếp tăng dần khi nào phạm vi tìm kiếm năm ở nửa sau của dãy?
Cho dãy số 0, 1, 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy” có phân tử giữa là bao nhiêu?
Trong thuật toán tìm kiếm nhị phân, việc tìm kiếm sẽ dừng khi nào?
Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng dần hoặc giảm dần, em có cách nào tìm nhanh hơn tìm kiếm tuần tự không?
Có 8 thẻ, mỗi thẻ có ghi một số nguyên trên đó. Tất cả các thẻ được sắp xếp thành dãy theo thứ tự không giảm của các số ghi trên đó và đặt sấp mặt ghi số xuống bàn để em không nhìn thấy. Cô giáo đọc một số, gọi là X chẳng hạn. Cần trả lời câu hỏi: Có hay không một thẻ ghi số X? Hãy sử dụng ít nhất số lần lật một thẻ lên xem mà vẫn trả lời được câu hỏi. Bạn Thanh An cho rằng chỉ cần không quá ba lần lật thẻ là trả lời được. Em đồng ý với Thanh An không? Vì sao?
Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy mô tả diễn biến từng bước tìm kiếm nhị phân để tìm kiếm x = 60 trong dãy trên.
Em hãy mô tả cách tra cứu, tìm giải nghĩa một từ trong từ điển. Có thể gọi cách tìm đó là áp dụng thuật toán tìm kiếm nhị phân không?
Hãy mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân?
Theo em, có phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân không? Giải thích tại sao?
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 *