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, chi tiết cùng với bài tập trắc nghiệm chọn lọc có đáp án 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ọc7.

Tin học lớp 7 Bài 2: Tìm kiếm nhị phân

A. Lý thuyết Tin học 7 Bài 2: Tìm kiếm nhị phân

1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự

Ý tưởng chia đôi dần để tìm một số trong một dãy số được minh họa bởi ví dụ sau đây:

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.

Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a₁ đến a₈. Lấy a₄ là số có vị trí giữa dãy: Vì x > a₄ nên nửa đầu dãy chắc chắn không chứa x = 44, sau đó cần tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a₅ đến a₈.

Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a₅ đến a₈. Lấy a₆ là số có vị trí giữa dãy; Vì x < a₆ nên nửa sau dãy chắc chắn không chứa x = 44, tiếp theo 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 từ a₅.

Phạm vi tìm kiếm chỉ còn một số. 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

- Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự.

- Ý tưởng: Chia đôi dần để giảm nhanh phạm vi tìm kiếm.

Hình 2.1: 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à a_m để so sánh với x. Nếu a_m = x thì kết thúc. Trái lại, sẽ có hai trường hợp:

- Nếu a_m < x thì chắc chắn không có x trong nửa đầu của dãy.

- Nếu x < a_m 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.

3. Phương pháp “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 đó, cho đến đi nhận được kết quả.

B. Bài tập trắc nghiệm Tin học 7 Bài 2: Tìm kiếm nhị phân

Câu 1. Điều kiện để áp dụng thuật toán nhị phân là:

A. Không có điều kiện.

B. Dãy đã được sắp xếp tăng dần.

C. Dãy đã được sắp xếp giảm dần.

D. Cả C và B

Câu 2. Điều kiện lặp trong bài toán tìm kiếm nhị phân là:

A. Kết quả= tìm thấy.

B. Phạm vi tìm kiếm dài hơn 1 và kết quả=chưa tìm thấy.

C. Xét hết dãy số

D. Cả A và C đều đúng

Câu 3. Trong thuật toán tìm kiếm nhị phân, việc tìm kiếm sẽ dừng khi:

A. Đã tìm kiếm hết dãy.

B.Đã tìm thấy kết quả mong muốn hoặc phạm vi tìm kiếm chỉ còn 1 số.

C. Đã tìm hết nửa dãy đầu.

D. Đã tìm hết nửa dãy sau.

Câu 4. Khẳng định nào sau đây là đúng khi nói về thuật toán tìm kiếm nhị phân?

A. Dãy không có thứ tự ta áp dụng thuật toán tìm kiếm nhị phân để: Không bỏ sót cho đến khi tìm thấy hoặc tìm hết dãy và không tìm thấy.

B. Điều kiện lặp trong bài toán tìm kiếm nhị phân là kết quả= tìm thấy.

C.Việc tìm kiếm nhị phân tìm đến phần tử cuối dãy khi tìm thấy kết quả mong muốn.

D. Chỉ có thể áp dụng thuật toán tìm kiếm nhị phân cho bài toán đã được sắp xếp.

Câu 5. 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à:

A. Nửa dãy đầu.

B. Nửa dãy sau.

C. Tất cả dãy.

D. Không có phạm vi.

Câu 11. Cho dãy số 2,4,6,8,9. Bài toán “Tìm vị trí của số 8 trong dãy”, cho kết quả là:

A. 1

B. 2

C. 3

D. 4

Câu 12. 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à:

A. 4

B. 2

C. 6

D. 8

Câu 13. Cho dãy số 0,1,2,4,6,8,9. Bài toán “Tìm số x=4 trong dãy” có số lần lặp là:

A. 0

B. 1

C. 2

D. 3

Câu 14. 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 đầu của dãy:

A. Khi số cần tìm lớn hơn phần tử giữa của phạm vi tìm kiếm.

B. Khi số cần tìm nhỏ hơn phần tử giữa của phạm vi tìm kiếm.

C. Khi số cần tìm lớn hơn phần tử đầu tiên của dãy.

D. Khi số cần tìm nhỏ hơn phần tử cuối cùng của dãy.

Câu 15. 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:

A. Khi số cần tìm lớn hơn phần tử giữa của phạm vi tìm kiếm.

B. Khi số cần tìm nhỏ hơn phần tử giữa của phạm vi tìm kiếm.

C. Khi số cần tìm lớn hơn phần tử đầu tiên của dãy.

D. Khi số cần tìm nhỏ hơn phần tử cuối cùng của dãy.

Xem thêm các bài tóm tắt lý thuyết Tin học 7 Cánh diều hay, chi tiết khác:

Lý thuyết Tin học 7 Bài 1: Tìm kiếm tuần tự

Lý thuyết Tin học 7 Bài 2: Tìm kiếm nhị phân

Lý thuyết Tin học 7 Bài 3: Sắp xếp chọn

Lý thuyết Tin học 7 Bài 4: Sắp xếp nổi bọt

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