SỞ GIÁO DỤC VÀ ĐÀO TẠO THÀNH PHỐ HẢI PHÒNG

HỘI THI
GIÁO
VIÊN
DẠY
GIỎI
CẤP
THÀNH
GIÁO
VIÊN
DẠY
GIỎI
CẤP
THÀNH
PHỐ
PHỐ

NHIỆT LIỆT CHÀO MỪNG QUÝ THẦY CÔ VỀ DỰ
HỘI THI GIÁO VIÊN DẠY GIỎI CẤP THCS
MÔN TIN HỌC: LỚP
Họ tên giáo viên: NGUYỄN THỊ LƯƠNG
Đơn vị: XÃ HÀ ĐÔNG

Thông tin trong
video cho các em
biết điều gì?

Bài toán:

CHỦ ĐỀ 5: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ
GIÚP CỦA MÁY TÍNH

BÀI 15: THUẬT TOÁN TÌM KIẾM
NHỊ PHÂN

BÀI 15: THUẬT TOÁN TÌM KIẾM
NHỊ PHÂN
 Nội dung:
1

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

2

Sắp xếp và tìm kiếm

1 THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Bài toán tìm kiếm khách hàng: Tìm địa chỉ của khách hàng có tên
“Trúc” trong danh sách sau đây:

1 THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Các bước tìm kiếm nhị phân
Sắp xếp danh sách theo tên bảng
chữ cái
Bước 1. Xét vị trí ở giữa của danh
sách
Bước 2. Xét vị trí ở giữa nửa sau
của danh sách
Bước 3. Xét vị trí ở giữa của
nửa sau còn lại của danh sách

Mai # Trúc
Mai < Trúc

Trang # Trúc
Trang < Trúc

Trúc = Trúc

Cách lấy vị trí nằm giữa danh sách

Lưu ý: “nửa trước” và “nửa sau” không gồm phần tư giữa

1 THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

Hoạt động cặp đôi

Nhiệm vụ 1:

Bài toán tìm kiếm số trong dãy số: Tìm xem số 8 có trong dãy số sau
không:
0

3

0

3

Tìm số 8 trong dãy số sau đây
4
5
8
16
Tìm
thấy
4
5
8
16
5#8
5<8

8=8

27

90

27

90

16#8
16>8
Thuật toán tìm kiếm nhị phân để tìm
ra kết quả của bài toán trên ta thực
hiện 3 bước.

1 THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
So sánh thuật toán tìm kiếm nhị phân với thật toán tìm kiếm tuần tự:
Tìm kiếm tuần tự
Tìm số 8 trong dãy số sau đây
0
3
4
5
8
16

27

90

Tìm
thấy

0

0

Tìm kiếm nhị phân
Tìm số 8 trong dãy số sau đây
3
4
5
8
16 27

3

4

5

Tìm
thấy
8
16

27

90

90

5#8 8=8 16#8
16>8
5<8
Thuật toán tìm kiếm tuần tự tìm ra kết
quả của bài toán trên ta thực hiện 5 bước.

Thuật toán tìm kiếm nhị phân để tìm
ra kết quả của bài toán trên ta thực
hiện 3 bước.

Nhìn vào ví dụ tìm số trong dãy số
? tìm kiếm tuần tự dãy số có đc sắp thứ tự khi tìm kiếm ko
?Còn tìm kiếm nhị phân có được sắp thứ tự khi tìm kiếmko
Vậy mục đích của sắp xếp thứ tự là gì?:………………………..

HS báo cáo

1 THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Mô tả thuật toán tìm kiếm nhị phân:
Mô tả thuật toá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. 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.
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 thuật toán.
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, vùng tìm kiếm mớ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 pjaanf tử nào (Bước 1)

Tìm số 4 trong dãy số sau đây
0
3
4
5
8
16 27
0

3

Tìm
thấy

4

5

8

16

27

90
90

3#4 4=4 5#4
3<4
5>4
Vậy để tìm ra kết quả của bài
toán trên ta thực hiện 3 bước

Nhiệm vụ 3:

Hoạt động nhóm máy

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.

1 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í số 5
1

2

3

4

An

Bình

Hòa

Liên

Vị trí ở
giữa
5
Mai

6

7

8

9

Phương

Trang

Trúc

Tước

Hòa # Mai
Hòa đứng trước Mai

Bước 2: Xét vị trí ở giữa của nửa trước của dãy là vị trí số 2
1

Vị trí ở
giữa
2

An

Bình
Bình # Hòa
Bình đứng
trước Hòa

3

4

5

6

7

8

9

Hòa

Liên

Mai

Phương

Trang

Trúc

Tước

Bước 3: Xét vị trí ở giữa của nửa sau của dãy là vị trí số 3.
1

2

Vị trí ở
giữa
3

An

Bình

Hòa

Tìm thấy
4

5

6

7

8

9

Liên

Mai

Phương

Trang

Trúc

Tước

Hòa = Hòa

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

Mô phỏng thuật toán tìm kiếm nhị phân
x = 44
 
a
i

a1
6
 1

a2
12
2

a3
18
3

a4
42
4

a5
44
44
5

a6
55
6

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.

a7
67
7

a8
94
8

Hộp kiến thức

Tiết … - Bài 15: TÌM KIẾM NHỊ PHÂN
Nếu lớn hơn là ở
nửa trước, nếu nhỏ
hơn là ở nửa sau

Bắt đầu từ vị trí
giữa danh sách

Danh sách
được sắp xếp

Chưa tìm thấy và còn
danh sách là còn tìm

Luôn so sánh với giá trị
của vị trí giữa danh sách

Tìm kiếm nhị phân

TRÒ CHƠI
“AI NHANH HƠN”





THỂ LỆ TRÒ CHƠI: AI NHANH HƠN
Học sinh tham gia trò chơi online trên
phần mềm kahoot bằng máy tính.
Mỗi câu hỏi có thời gian giới hạn là 10
giây, chọn đáp án đúng nhanh nhất để
được điểm cao.
Không trao đổi với nhóm khác, không sử
dụng tài liệu, chơi nghiêm túc và trung
thực.
Kết quả được xếp hạng tự động sau khi
kết thúc trò chơi. Bạn nào/nhóm nào
có kết qủa nhanh nhất sẽ nhận được
phần quà.

KAHOOT…….

CHÚC MỪNG CÁC BẠN

Bài 1: 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 đó?
Em tìm một từ tiếng Anh trong quyển từ điển bằng cách chia đổi
quyển từ điển, tìm một từ bất kì ở giữa quyển từ điển và so sánh
với từ cần tìm. Nếu tìm thấy từ đó thì sẽ kết thúc việc tìm kiếm.
Nếu chưa em lại tiếp tục chia quyển từ điển theo nửa thích hợp, đến
khi nào tìm được từ cần tìm thì kết thúc. Em dùng cách này vì
nhanh chóng và thuận tiện hơn là tìm kiếm từng từ trong bảng chữ
cái.

Bài 2: Thực hành: Em hãy tìm kiếm thông tin trên Internet để lập danh sách
khoảng 10 cuốn sách mà em yêu thích và đơn giá của mỗi cuốn sách. Sau đó
thực hiện thuật toán tìm kiếm nhị phân để tìm cuốn sách mà em thích nhất trong
danh sách vừa tìm được và cho biết đơn giá của cuốn sách đó.
Bước 1: Tìm kiếm thông tin trên Internet, lập bảng danh sách khoảng 10
cuốn sách và đơn giá của mỗi cuốn sách
Bước 2: Sắp xếp tên sách theo thứ tự của bảng chữ cái
Bước 3: Chỉ ra tên một cuốn sách mà em thích nhất
Bước 4: Liệt kê các bước thực hiện thuật toán tìm kiếm nhị phân để tìm cuốn
sách mà em thích nhất trong danh sách ở bước 2
Bước 5: Ghi ra đơn giá của cuốn sách tìm thấy ở bước 4

HƯỚNG DẪN HỌC Ở NHÀ
 Ôn lại nội dung bài đã học.
 Chuẩn bị giờ sau: Đọc trước nội
dung Bài 16: “Thuật toán sắp
xếp”

THE END

Mô phỏng: Bài toán tìm kiếm tuần tự
Cho dãy số: 18, 94, 42, 44, 6, 55, 12, 67. Tìm xem số 44 có ở trong dãy không?
18 ≠ 4494 ≠ 4442 ≠ 4444 = 44
Dãy
số

18

94

42

44

6

55

12

67

Lần
lặp

1

2

3

4

-

-

-

-

i
KL: Với lần lặp thứ 4 thì tìm thấy số cần tìm là 44

?Để mô tả thuật toán có mấy cách để mô tả mà em đã được học.
HS có 2 cách
? Em hãy mô tả bài toán tìm địa chỉ khách hàng “Thanh Trúc bằng ngôn ngữ tự
nhiên hoặc sơ đồ khối

Câu hỏi cuối bài phần nhị phân
Câu 4:
Câu 1:
Điều kiện dừng của tìm kiếm nhị phân là:
Tìm kiếm nhị phân chỉ áp dụng cho dãy dữ liệu nào sau đây? A. Khi duyệt hết dãy
A. Dãy bất kỳ
B. Khi tìm thấy hoặc không còn phần tử để tìm
B. Dãy đã được sắp xếp
C. Khi so sánh 2 lần
C. Dãy ngẫu nhiên
D. Khi gặp số lớn nhất
D. Dãy không có quy luật
Đáp án: B
Đáp án: B
Câu 5:
Câu 2:
Trong dãy [1, 3, 5, 7, 9], tìm số 1 bằng tìm kiếm nhị
Trong tìm kiếm nhị phân, phần tử được so sánh đầu tiên là: phân, bước đầu so sánh với:
A. Phần tử đầu tiên
A. 1 B. 3 C. 5 D. 9 Đáp án: C
B. Phần tử cuối cùng
Câu 6. Thuật toán tìm kiếm nhị phân cần thực hiện bao nhiêu bước để thông
C. Phần tử ở giữa dãy
báo không tìm thấy số 10 trong danh sách [2, 5, 8, 11, 14, 17]?
D. Phần tử bất kỳ
A. 2.
B. 3.
C. 4.
D. 5.
Đáp án: C
Câu 7:
Câu 3:
Sau mỗi lần so sánh trong tìm kiếm nhị phân, số phần tử cần tìm sẽ:
Nếu giá trị cần tìm nhỏ hơn giá trị ở giữa, ta sẽ: A. Giảm đi một nửa
B. Giữ nguyên
A. Tìm bên phải
C. Tăng lên
D. Giảm 1 phần tử
B. Tìm bên trái
Đáp án: A
C. Dừng lại
Câu 8. Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy “Mai”
D. Tìm lại từ đầu
trong danh sách [Hoa", "Lan”, ”Ly”, ”Mai”, ”Phong”, ”Vi”]?
Đáp án: B
a) 1.
b) 2.
c) 3.
d) 4.