ề
CĐ

 Tin 7

Về kiến thức:
-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ạ.

Về năng lực:
2.1. Năng lực chung
-Năng lực tự chủ, tự học: Học sinh chủ động và tích cực thực hiện
nhiệm vụ học tập; vận dụng được những kiến thức, kĩ năng đã học để
hoàn thành nhiệm vụ.
-Năng lực giao tiếp và hợp tác: HS có khả năng hoạt động nhóm để
hoàn thành các nhiệm vụ học tập.
-Năng lực giải quyết vấn đề và sáng tạo: HS đưa ra thêm một số ví dụ
về các tìm kiếm nhị phân và sắp xếp.
2.2. Năng lực Tin học
-Nhận biết các hoạt động sử dụng tìm kiếm nhị phân.
-Viết được thuật toán dưới dạng liệt kê hoặc sơ đồ khối.
-Lập được bảng mô phỏng thuật toán.

 Tin 7

ề
CĐ

NỘI
DUNG

1 Thuật toán tìm kiếm nhị phân.

TRỌNG 2 Sắp xếp và tìm kiếm
TÂM

KHÁM
PHÁ

ề
CĐ

 Tin 7

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?
Để tìm kiếm tên khách hàng trong danh sách được dễ dàng hơn,
bạn An nên sắp xếp tên khách hàng theo thứ tự trong bảng chữ cái.

HOẠT ĐỘNG
1. Thuật toán tìm kiếm nhị
phân.

1. Thuật toán tìm kiếm nhị phâ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.1

1. Thuật toán tìm kiếm nhị phân.
*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 tìm ở 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).

1. Thuật toán tìm kiếm nhị phân.
Các bước để An tìm khách hàng tên “Trúc” trong danh sách ở Hình
15.1 theo thuật toán tìm kiếm nhị phân như sau:
Bước 1. Xét vị trí ở giữa của dãy, đó là vị trí số 5.

1. Thuật toán tìm kiếm nhị phân.
Bước 2. Xét vị trí ở giữa của nửa sau của dãy là vị trí số 7.

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

Vì sau bước 3 đã tìm thấy tên khách hàng nên thuật toán kết thúc.

1. Thuật toán tìm kiếm nhị phân.
Sắp xếp và tìm kiếm
Nghiên cứu và thảo luận
Em hãy cho biết thuật
*Thuật toán tìm kiếm tuần tự phải thực
toán tìm kiếm tuần tự
hiện 8 bước để tìm khách hàng tên Trúc.
phải thực hiện bao
*Số bước thực hiện của thuật toán tìm
nhiêu bước để tìm
kiếm tuần tự nhiều hơn so với số bước thực
khách hàng tên Trúc
hiện thuật toán tìm kiếm nhị phân vì thuật
?
như ở Hình 15.1? Em
toán tìm kiếm tuần tự sẽ tìm kiếm lần lượt
hãy so sánh số bước
từ đầu danh sách cho đến khi tìm được tên
thực hiện của thuật toán
của bạn Trúc nên sẽ mất 8 lần lặp, còn
tìm kiếm tuần tự với số
thuật toán tìm kiếm nhị phân so sánh giá trị
bước thực hiện thuật
ở giữa danh sách nên sẽ nhanh chóng hơn
toán tìm kiếm nhị phân.

ề
CĐ

 Tin 7

1. Thuật toán tìm kiếm nhị phân.
Sắp xếp và tìm kiếm
Nghiên cứu và thảo luận
Theo em trước khi thực
Trước khi thực hiện thuật toán tìm kiếm
hiện thuật toán tìm kiếm
nhị phân, danh sách khách hàng cần
nhị phân, danh sách khách
phải được sắp xếp theo quy tắc (theo
hàng cần thỏa mãn điều
bảng chữ cái, số thứ
? tự tăng dần hoặc
kiện gì? Nếu không thỏa
giảm dần). Nếu không thỏa mãn điều
mãn điều kiện đó, thuật
kiện đó, thuật toán tìm kiếm nhị phân
toán tìm kiếm nhị phân có
không thực hiện được.
thực hiện được không?

1. Thuật toán tìm kiếm nhị phân.
Thuật toán tìm kiếm nhị phân
Nghiên cứu và thảo luận
Thuật toán tìm kiếm thu hẹp danh sách
Thế nào là thuật toán
tìm kiếm chỉ còn một? nửa, gọi là tìm kiếm
tìm kiếm nhị phân?
nhị phân.

*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 trước là “nhỏ hơn”
kí tự đứng sau trong bảng chữ cái.

1. Thuật toán tìm kiếm nhị phân.
Thuật toán
Nghiên cứu và thảo luận
Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên:
Em
hãy
mô tả thuật
toán tìm
kiếm nhị
phân bằng
ngôn ngữ
tự nhiên?

-B1. 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.
-B2. 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.
-B3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận
? giữa” và kết thúc.
“giá trị cần tìm xuất hiện tại vị trí
-B4. 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.
-B5. Lặp lại từ B1 đến B4 cho đến khi tìm thấy giá trị cần tìm
(B3) hoặc vùng tìm kiếm không còn phần tử nào (B1).

1. Thuật toán tìm kiếm nhị phân.
Thuật toán tìm kiếm nhị phân
Nghiên cứu và thảo luận
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
theo thứ tự từ nhỏ đến lớn. Bắt đầu từ vị trí
ở giữa danh sách.
Em hãy trình bày về -Tại mỗi bước lặp, so sánh giá trị cần tìm
thuật toán tìm kiếm nhị với giá trị của vị trí? giữa danh sách, nếu
phân?
bằng thì dừng lại, nếu nhỏ hơn thì tìm
trong nửa trước của danh sách, nếu lớn hơn
thì tìm trong nửa sau của danh sách.
-Chừng nào chưa tìm thấy và vùng tìm
kiếm còn phần tử thì còn tìm tiếp.

ề
CĐ

 Tin 7

1. Thuật toán tìm kiếm nhị phân.
Bài tập: 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 "Hòa" trong danh sách ở Hình 15.1.

BÀI TẬP

Hướng dẫn giải:

Danh sách tên khách hàng theo thứ tự trong bảng chữ cái:
An Bình Hoà Liên Mai Phương Trang Trúc Tước
*Thuật toán tìm kiếm nhị phân:
Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí thứ 5
So sánh “Hoà” và “Mai” vì “H” đứng trước “M” trong bảng chữ cái
nên bỏ đi nửa sau danh sách.
Bước 2: Xét vị trí ở giữa của nửa trước của dãy là vị trí số 2.
So sánh “Hoà” và “Bình” vì “H” đứng sau “B” trong bảng chữ cái
nên bỏ đi nửa trước danh sách.
An Bình Hoà Liên Mai Phương Trang Trúc Tước

 Tin 7

ề
CĐ

BÀI TẬP

Hướng dẫn giải:

Danh sách tên khách hàng theo thứ tự trong bảng chữ cái:
An Bình Hoà Liên Mai Phương Trang Trúc Tước
*Thuật toán tìm kiếm nhị phân:
Bước 3: Xét vị trí ở giữa của nửa sau của dãy là vị trí số 3.
So sánh “Hoà” và “Hoà” vì hai giá trị bằng nhau, đã tìm thấy tên
khách hàng nên thuật toán kết thúc.
1
2
3
4
5
6
7
8
9
An Bình Hoà Liên Mai Phương Trang Trúc Tước

HOẠT ĐỘNG
2. Sắp xếp và tìm kiếm

2. Sắp xếp và tìm kiếm.
*Trong 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 khi 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. Nhờ việc danh sách đã được sắp xếp, tại mỗi bước, thuật toán tìm kiếm
nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn một nửa.

ề
CĐ

 Tin 7

2. Sắp xếp và tìm kiếm.
Sắp xếp và tìm kiếm
Nghiên cứu và thảo luận
Em hãy nêu tác dụng
Sắp xếp giúp cho việc tìm kiếm được
?
của sắp xếp và tìm
thực hiện nhanh hơn.
kiếm?

 Tin 7

ề
CĐ

Trò chơi tìm số:

Stt
DS tăng dần

1T

1
?9

1P

2T

2P

2 3 4 5 6 7 8 9 10
? 15
? 18
? 21
? 24
? 26
? 28
? 30
? 32
?
12
Bạn muốn tìm số mấy
trong khoảng từ 135?

 Tin 7

ề
CĐ

2. Sắp xếp và tìm kiếm.
Bài tập
Em hãy nêu ví dụ
Ví dụ trong thực tế cho thấy mối liên quan
trong thực tế cho thấy
giữa sắp xếp và tìm? kiếm là tra từ điển
mối liên quan giữa sắp
Tiếng Anh.
xếp và tìm kiếm?

LUYỆN TẬP

Bài tập
Thuật toán tìm kiếm nhị phân được sử dụng trong trường
hợp nào?
Tìm một phần tử trong danh sách bất kì.
Tiến trước phần tử trong danh sách đã được sắp xếp.
Cả A, B đều đúng.
Cả A, B đều sai.

Bài tập
Điều gì xảy ra khi thuật toán tìm kiếm nhị phân không
tìm thấy giá trị cần tìm trong danh sách?
Tiếp tục tìm kiếm và không bao giờ kết thúc.
Thông báo Tìm thấy và tiến tiếp xem còn phần tử nào
khác nữa không.
Thông báo Tìm thấy và kết thúc.
Thông báo "Không tìm thấy” và kết thúc.

Bài tập
Điều kiện dừng trong thuật toán tìm kiếm nhị phân là gì?
Khi tìm đến giá trị cuối cùng trong danh sách.
Khi chưa tìm thấy.
Khi chưa tìm thấy và chưa hết danh sách.
Khi đã tìm thấy hoặc khi đã hết danh sách.

Bài tập
Thực hiện thuật toán tìm kiếm nhị phân để tìm số 10 trong
danh sách [2, 4 ,6, 8, 10, 12]. Đầu ra của thuật toán là?
Thông báo “Không tìm thấy”.
Thông báo “Tìm thấy” ở vòng lặp thứ 3.
Thông báo “Tìm thấy” ở vòng lặp thứ 2.
Thông báo “Tìm thấy” sau khi tìm hết danh
sách.

Bài tập
Tại mỗi bước lặp, thuật toán tìm kiếm nhị phân sẽ:
Thu hẹp danh sách tìm kiếm chỉ còn một nửa.
Danh sách sẽ được sắp xếp lại.
Các phần tử trong danh sách sẽ giảm một nửa.
Đáp án khác.

Bài tập

Thuật toán tìm kiếm nhị phân cần thực hiện bao nhiêu
bước để thông báo không tìm thấy số 10 trong danh sách
[2, 5, 8, 11, 14, 17]?

2
3
4
5

Bài tập
Thuật toán tìm kiếm nhị phân thực hiện trên danh sách
nào?
Đã được hoán đổi.
Đã được sắp xếp.
Đã được chỉnh sửa.
Cả A, B và C.

Bài tập
Trong thuật toán tìm kiếm nhị phân thì vùng tìm kiếm
lúc ban đầu là gì?
Nửa trước danh sách.
Nửa sau danh sách.
Toàn bộ danh sách.
Đáp án khác.

Bài tập
Điều gì xảy ra khi thuật toán tìm kiếm nhị phần không
tìm thấy giá trị cần tìm trong danh sách?
Tiếp tục tìm kiếm và không bao giờ kết thúc.
Thông báo Tìm thấy và tiến tiếp xem còn phần tử nào
khác nữa không.
Thông báo Tìm thấy và kết thúc.
Thông báo "Không tìm thấy và kết thúc“.

Bài tập
Lợi ích của việc sắp xếp trong tìm kiếm là?
Giúp tìm kiếm chính xác hơn.
Giúp tìm kiếm nhanh hơn.
Giúp tìm kiếm đầy đủ hơn.
Cả A, B và C.

Bài tập
Chọn câu diễn đạt đúng hoạt động của thuật toán tìm
kiếm nhị phân?
Tìm trên danh sách đã sắp xếp, bắt đầu từ đầu danh sách,
chừng nào chưa tìm thấy hoặc chưa tìm hết thị còn tìm tiếp.
Tìm trên danh sách đã sắp xếp, bắt đầu từ giữa danh sách,
chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
Tìm trên danh sách bất kì, bắt đầu từ giữa danh sách, chừng
nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
Tiến trên danh sách bất kì, bắt đầu từ đầu danh sách, chừng
nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

Bài tập
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ì:
Tìm trong nửa đầu của danh sách.
Tìm trong nửa sau của danh sách.
Dừng lại.
Tìm trong nửa đầu hoặc nửa sau của danh sách.

Bài tập
Điều kiện lặp của thuật toán tìm kiếm nhị phân là gì?
Chưa tìm thấy phần tử cần tìm.
Chưa hết danh sách.
Chưa tìm thấy phần tử cần tìm hoặc chưa hết danh sách.
Chưa tìm thấy phần tử cần tìm và chưa hết danh
sách.

Bài tập
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?
Tìm một số trong một danh sách.
Tìm một từ tiếng anh trong quyển từ điển.
Tìm tên một bài học trong quyển sách.
Tìm tên một nước trong danh sách.

Bài tập

Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm
thấy “Mai” trong danh sách [Hoa", "Lan”, ”Ly”, ”Mai”,
”Phong”, ”Vi”]?

1
2
3
4

Bài tập

Thuật toán tìm kiếm nhị phân cần thực hiện bao nhiêu
bước lặp để thông báo không tìm thấy số 15 trong danh
sách [3, 5, 7, 11, 12, 25]?

1
2
3
4

Bài tập
Tư tưởng của thuật toán tìm kiếm nhị phân là gì?
Tìm kiếm dựa vào cây tìm kiếm.
Tìm kiếm từ đầu đến cuối dãy.
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 trước hay ở nửa
sau của danh sách.

So sánh X lần lượt với các phần tử a1, a2, …,
an.

Bài tập
Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy
Thailand trong danh sách tên các nước sau:
Brunei, Campodia, Laos, Myanmar, Singpore, Thailand,
Vietnam

1

2

3

4

Bài tập
Trong các đặc điểm sau, đặc điểm nào là của thuật toán
tìm kiếm tuần tự:?
Thực hiện tìm kiếm từ đầu đến cuối mảng.
Chạy nhanh hơn tìm kiếm nhị phân.
Cần mảng đã được sắp xếp.
Cần chia mảng thành các phần.

Bài tập
Tìm kiếm nhị phân hoạt động hiệu quả nhất với danh
sách nào trong các dạng danh sách sau đây?
Không sắp xếp.
Đã được sắp xếp.
Liệt kê.
Được sắp xếp giảm dần.

Bài tập
ỗi lần thực hiện tìm kiếm nhị phân, thuật toán loại bỏ
phần tử (nhóm phần tử) nào trong các ý sau đây?
Một nửa danh sách.
Một phần tử.
Một nửa số phép so sánh.
Không loại bỏ gì.

PHIẾU SỐ 10 CD5B15(B, H, V, V):
Nhóm bạn Bình và bạn An được thầy giáo yêu cầu xây dựng thuật
toán tìm kiếm phần tử có giá trị bằng x trong dãy gồm n số nguyên Đ/S
cho trước. Bình và An phân vân không biết nên sử dụng thuật toán
tìm kiếm tuần tự hay tìm kiếm nhị phân?
a) Thuật toán tìm kiếm tuần tự kiểm tra từng phần tử trong danh
sách cho đến khi tìm thấy phần tử cần tìm hoặc đã kiểm tra hết danh Đ
?
sách.
b) Thuật toán tìm kiếm nhị phân hoạt động hiệu quả trên danh sách
S
?
chưa được sắp xếp.
c) Thuật toán tìm kiếm nhị phân chia danh sách thành hai phần và
Đ
?
so sánh giá trị cần tìm với giá trị của phần tử ở giữa danh sách.
d) Trong thuật toán tìm kiếm nhị phân, nếu dãy số có 16 phần tử thì
?
S
số phép so sánh tối đa là 8.

Em hãy điền các cụm từ: giá trị cần tìm xuất hiện ở vị trí giữa, nửa sau,
“Không tìm thấy”, nửa trước vào chỗ chấm (...) được đánh số trong các câu
sau để được mô tả chính xác về thuật toán tìm kiếm nhị phân.
-B1: Nếu vùng tìm kiếm không có phần tử nào thì kết luận 1- “Không tìm
?
.... (1)..... và thuật toán kết thúc.
thấy”
-B2.Xác định vị trí giữa vùng tìm kiếm. Vị trí này chia vùng
2- giá trị cần
tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.
? hiện
-B3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết tìm xuất
ở vị trí giữa
luận .....(2)...... và thuật toán kết thúc.
-B4. 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...(3)... 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) thì vùng
tìm kiếm mới được thu hẹp lại, chỉ còn ... (4)... của dãy.
-B5. Lặp lại từ B1 đến B5 cho đến vùng tìm kiếm không khi
còn phần tử nào (B1) hoặc tìm thấy giá trị cần tìm (B3).

3- nửa ?trước
4- nửa ?sau

ề
CĐ

 Tin 7

LUYỆN TẬP
Hãy ghép mỗi nội dung ở cột A với những nội dung phù hợp ở cột
B để xác định đầu vào và đầu ra của thuật toán tìm kiếm nhị phân.
A
B
Ghép:
a) Thông báo tìm thấy và chỉ ra vị trí cần tìm. 1- C?
1) Đầu vào
b) Thông báo không tìm thấy.
1- D?
c) Giá trị cần tìm.
2- A?
2) Đầu ra
d) Danh sách đã sắp xếp.
2- B?

ề
CĐ

 Tin 7

LUYỆN TẬP
Cho danh sách tên các nước sau đây:
Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal,
Greendland, 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.