KHỞI
ĐỘNG

TRÒ
CHƠI

TIẾP SỨC
Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Sử dụng thuật toán tìm kiếm tuần tự điền thông tin vào bảng sau:
Số cần
tìm
16
8
2
58

Vị trí trong
dãy

Số lần lặp

TRÒ
CHƠI

TIẾP SỨC
Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Sử dụng thuật toán tìm kiếm tuần tự điền thông tin vào bảng sau:
Số cần
tìm
16
8
2
58

Vị trí trong
dãy

Số lần lặp

TRÒ
CHƠI

TIẾP SỨC
Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Sử dụng thuật toán tìm kiếm tuần tự điền thông tin vào bảng sau:
Số cần
tìm
16
8
2

Vị trí trong
dãy
5
2
Không tìm
thấy

Số lần lặp
5
2
9

BÀI 13: THUẬT TOÁN TÌM KIẾM (tt)
2. Thuật toán tìm kiếm nhị phân:

KHÁM
PHÁ

BÀI 13: THUẬT TOÁN TÌM KIẾM (tt)
2. Thuật toán tìm kiếm nhị phân:
Vị
trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Sử dụng thuật toán tìm kiếm tuần tự điền thông tin
vào bảng sau:
Số cần
Vị trí
tìm
trong dãy

Số
lần
lặp

16
8
2
58

Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân.

Vị trí thẻ giữa dãy là phần nguyên
của phép chia:
(vị trí thẻ đầu + vị trí thẻ cuối) / 2
Vị
trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Vị trí thẻ giữa dãy là phần nguyên
của phép chia:
(vị trí thẻ đầu + vị trí thẻ cuối) / 2
Vị
trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Vị trí thẻ giữa dãy là phần nguyên
của phép chia:
(vị trí thẻ đầu + vị trí thẻ cuối) / 2
Vị
trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Vị trí thẻ giữa dãy là phần nguyên
của phép chia:
(vị trí thẻ đầu + vị trí thẻ cuối) / 2
Vị
trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:
Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Sử dụng thuật toán tìm kiếm tuần tự điền thông tin vào bảng sau:
Số cần
tìm
16
8
2
58

Vị trí trong
dãy

Số lần
lặp

Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Số cần
tìm

16
8
2
58

Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân

Vị trí trong
dãy

5

Số lần
lặp

1

Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Số cần
tìm

16
8
2
58

Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân

Vị trí trong
dãy

5
2

Số lần
lặp

1
2

Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Số cần
tìm

16
8
2
58

Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân

Vị trí trong
dãy

5
2
Không tìm thấy

Số lần
lặp

1
2
3

Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Số cần
tìm

16
8
2
58

Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân

Vị trí trong
dãy

5
2

Số lần
lặp

1

Không tìm thấy

2
3

9

4

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:
Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Số cần
tìm

Vị trí trong
dãy

16
8
2
58

5
2
Không tìm thấy
9

Số lần lặp
tìm kiếm nhị
phân
1
2
3
4

Số lần lặp
tìm kiếm
tuần tự
5
2
9
9

Tại sao sử dụng
thuật toán tìm
kiếm nhị phân
nhanh hơn?

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:
Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Số cần
tìm

Vị trí trong
dãy

16
8
2
58

5
2
Không tìm thấy
9

Số lần lặp
tìm kiếm nhị
phân
1
2
3
4

Số lần lặp
tìm kiếm
tuần tự
5
2
9
9

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:
Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Sắp xếp tăng hoặc giảm

Để thực hiện tìm
kiếm nhị phân,
yêu cầu dãy số
phải như thế nào?

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:
Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Sắp xếp tăng hoặc giảm

Việc sắp xếp
giúp gì trong
việc tìm kiếm?

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:
Vị trí

1

2

3

4

5

6

7

8

9

d.số

5

8

9

15

16

20

35

41

58

Sắp xếp tăng hoặc giảm

Em hãy cho ví
dụ về dữ liệu
trong cuộc sống
đã sắp xếp để
dễ tìm kiếm ?

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:
Em hãy sử dụng thuật toán tìm
kiếm nhị phân để điền thông tin
vào bảng sau:
Tên khách
hàng
Huy
Bình
Bảo
Nam

Có địa
chỉ?

Số lần
lặp

có

1

STT Tên khách hàng
Địa chỉ
1 An
15 Ngô Quyền
2 Bình
210 Nguyễn Du
3
4
5
6

Dung
Huy
Khanh
Linh

102 Đoàn Thị Điểm
76 Nguyễn Huệ
13 Trần Hưng Đạo
309 Lê Hồng Phong

7

Nam

27 Hai Bà Trưng
Danh sách khách hàng

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:
Em hãy sử dụng thuật toán tìm
kiếm nhị phân để điền thông tin
vào bảng sau:
Tên khách
hàng

Có địa
chỉ?

Số lần
lặp

Bình

có

2

Bảo
Nam

không
có

3
3

STT Tên khách hàng
Địa chỉ
1 An
15 Ngô Quyền
2 Bình
210 Nguyễn Du
3
4
5
6

Dung
Huy
Khanh
Linh

102 Đoàn Thị Điểm
76 Nguyễn Huệ
13 Trần Hưng Đạo
309 Lê Hồng Phong

7

Nam

27 Hai Bà Trưng
Danh sách khách hàng

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:
- Áp dụng với dãy giá trị đã được sắp xếp.
- Ở mỗi lần lặp thực hiện:
B1. So sánh giá trị cần tìm với giá trị của phần tử giữa dãy đang xét.
B2. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.
B3. Nếu nhỏ hơn thì xét dãy ở nửa trước, nếu lớn hơn thì xét dãy ở nửa sau.
B4. Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc, ngược lại quay về bước 1.
- Sắp xếp giúp viêc tìm kiếm được thực hiện nhanh hơn, hiệu quả hơn.

BÀI 13: THUẬT TOÁN TÌM KIẾM (tt)
2. Thuật toán tìm kiếm nhị phân:

LUYỆN TẬP

THÁCH ĐẤU
Luật chơi:
Đội A sẽ nhận 1 câu hỏi, và sử dụng câu hỏi đó thánh đấu với 1 trong 3 đội còn lại.
Nếu đội được thánh đấu (B) trả lời đúng sẽ nhận được 1 phần quà, nếu sai, đội A sẽ trả lời.
Nếu đội A trả lời đúng sẽ nhận được 1 phần quà và ra hình phạt cho đội B.
Nếu đội A trả lời sai, 2 đội còn lại sẽ trả lời để nhận phần quà.

Câu 1. Áp dụng thuật toán tìm kiếm tuần tự để tìm
ra tỉnh có biển số xe là 25. Cho biết em đã thực
hiện bao nhiêu lần lặp.

Đáp án: Lai Châu

STT

Tên tỉnh

Số
xe

1

An Giang

67

2

72

3

Bà Rịa – Vũng
Tàu
Bình Phước

4

Cà Mau

69

5

Điện Biên

27

6

Gia Lai

81

7

Khánh Hoà

79

8

Lai Châu

25

9

Nam Định

18

Yên Bái

21

10

93

Câu 2. Áp dụng thuật toán tìm kiếm nhị phân để
tìm biển số xe của tỉnh Lai Châu. Cho biết em đã
thực hiện bao nhiêu lần lặp.

Đáp án: 2

STT

Tên tỉnh

Số
xe

1

An Giang

67

2

72

3

Bà Rịa – Vũng
Tàu
Bình Phước

4

Cà Mau

69

5

Điện Biên

27

6

Gia Lai

81

7

Khánh Hoà

79

8

Lai Châu

25

9

Nam Định

18

Yên Bái

21

10

93

Câu 3. Số lần lặp mà em thực hiện của câu 1 ít hơn
hay câu 2 ít hơn? Tại sao?

Đáp án: Câu 2 ít hơn, vì sử dụng
thuật toán tìm kiếm nhị phân

STT

Tên tỉnh

Số
xe

1

An Giang

67

2

72

3

Bà Rịa – Vũng
Tàu
Bình Phước

4

Cà Mau

69

5

Điện Biên

27

6

Gia Lai

81

7

Khánh Hoà

79

8

Lai Châu

25

9

Nam Định

18

Yên Bái

21

10

93

Câu 4. Có thể dùng thuật toán tìm kiếm nhị phân
để tìm tên tỉnh khi biết số xe không? Tại sao?

Đáp án: Không, vì số xe
chưa được sắp xếp

STT

Tên tỉnh

Số
xe

1

An Giang

67

2

72

3

Bà Rịa – Vũng
Tàu
Bình Phước

4

Cà Mau

69

5

Điện Biên

27

6

Gia Lai

81

7

Khánh Hoà

79

8

Lai Châu

25

9

Nam Định

18

Yên Bái

21

10

93

BÀI 13: THUẬT TOÁN TÌM KIẾM(tt)
2. Thuật toán tìm kiếm nhị phân:
- Áp dụng với dãy giá trị đã được sắp xếp.
- Ở mỗi lần lặp thực hiện:
B1. So sánh giá trị cần tìm với giá trị của phần tử giữa dãy đang xét.
B2. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.
B3. Nếu nhỏ hơn thì xét dãy ở nửa trước, nếu lớn hơn thì xét dãy ở nửa sau.
B4. Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc, ngược lại quay về bước 1.
- Sắp xếp giúp viêc tìm kiếm được thực hiện nhanh hơn, hiệu quả hơn.