CHÀO MỪNG THẦY CÔ VỀ DỰ
GIỜ TIẾT DẠY GVG VÒNG HUYỆN

ĐỘNG
Câu 1: Điều kiện dừng thuật toán tìm kiếm
tuần tự là gì?
A. Tìm thấy phần tử cần tìm.

B. Tìm thấy phần tử cần tìm
và đã hết danh sách.

C. Đã hết danh sách.

D. Tìm thấy phần tử cần
tìm hoặc đã hết danh sách.

Câu 2: Thực hiện thuật toán tìm kiếm tuần tự để tìm
số 10 trong danh sách [2, 6, 8, 4, 10, 12]. Đầu ra của
thuật toán là?
A. Thông báo “Tìm thấy”, giá
trị cần tìm tại vị trí thứ 5 của
danh sách.

C. Thông báo “Không tìm
thấy”.

B. Thông báo “Tìm thấy”.

D. Thông báo “Tìm thấy”, giá
trị cần tìm tại vị trí thứ 6 của
danh sách.

Câu 3 : Em hãy quan sát cho biết thuật toán tìm kiếm tuần tự cần
bao nhiêu bước để tìm thấy số 79.

* Mô tả

BÀI 15: 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

HỌC SINH THỰC HÀNH

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).

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

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.

VD. Để tìm số 37 trong dãy số sau:

Quan sát và so sánh thuật toán tìm kiếm nhị phân và tìm kiếm
tuần tự Tìm kiếm cách nào nhanh hơn?

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).

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.

Bước 1. A úp lần lượt 10 chiếc thẻ lên bàn theo
thứ tự các số từ bé đến lớn.

2

3

5

6

8

9

11

15

16

18

Bạn. B cho A biết con số mình cần tìm: VD cần tìm số 11

2

3

5

6

8

9

11

15

16

18

8

9

11

15

16

18

9

11

15

Câu 1: 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
A. 1 bước          

    
                       
C. 3 bước
                      

 B. 2 bước
D. 4 bước

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

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

SƠ ĐỒ TƯ DUY

L

L
LOVE

G
S

TẠML BIỆT VÀ HẸN GẶP LẠI
PIRCE

T
H
L