Lớp 10A8
Kính chào quý thầy cô giáo
đến dự giờ !

Kiểm tra bài cũ
Kiểm tra bài cũ
Nhắc lại ý tưởng của thuật
toán tìm kiếm tuần tự?

Trả lời
Trả lời
Bài toán tìm kiếm:
•
Input: Dãy A gồm N số hạng a
1
, a
2
, …, a
N

và khóa k
Output: Vị trí của số hạng bằng k trong dãy
A hoặc thông báo không tìm thấy
•
Ý tưởng: So sánh tuần tự a
i
với khóa k (với
1≤ i ≤ N), nếu a
i
= k thì đưa ra i hoặc thông

hẹp phạm vi tìm kiếm bằng cách so sánh
k với số hạng ở giữa dãy
k với số hạng ở giữa dãy
a
1
, a
2
, …, a
(N+1)/2
, … a
N-1
, a
N
Nếu k < a
(N+1)/2
Tìm kiếm trong phạm vi này
Nếu k > a
(N+1)/2
Tìm kiếm trong phạm vi này
Nếu k = a
[(N+1)/2]
thì thông báo chỉ số (N+1)/2
< a
(N+1)/2
> a
(N+1)/2

Tiếp tục: Xác định lại vị trí đầu, giữa, cuối trong
dãy mới:
Dau = 6; Cuoi = 10

Cho dãy A tăng a
Cho dãy A tăng a
1
1
, a
, a
2
2
, …, a
, …, a
10
10
và k = 55
và k = 55
22 40 55
Làm thế nào để tìm ra vị trí của số hạng có giá trị bằng 55 nhanh nhất?
a
1
a
2
a
3
a
4
a
5
a
6
a
7

,
a
2
, , a
N
và khóa k
Bước 2: Dau ← 1 , Cuoi ← N
Bước 3: Giua ← [(Dau+ Cuoi)/2]
Bước 4: Nếu a
Giua
= k thì thông
báo chỉ số Giua, rồi kết thúc.
Bước 5: Nếu a
Giua
> k thì Cuoi =
Giua - 1, rồi chuyển đến bước 7
Bước 6: Dau ← Giua + 1
Bước 7: Nếu Dau > Cuoi thì
thông báo dãy A không có số
hạng có giá trị bằng k, rồi kết thúc
Bước 8: Quay lại bước 3
Thuật
Thuật
toán
toán
Đưa ra Giua,
rồi kết thúc
Nhập N; dãy a
1
,. . . ,a

Thông báo K không có
trong dãy số A, rồi kết thúc
Cuoi  Giua -1
A
Giua
= K?
Nhập N; dãy a1,. . . ,aN ; K
Dau  1 ; Cuoi  N
Dau  Giua + 1
Sai
A
Giua
> K?
Dau>Cuoi?
Giua  [ (Dau + Cuoi)/2 ]
Đưa ra Giua
rồi kết thúc
Sai
Đúng
Đúng
Sai
Đúng
N = 10 K = 21
Giua
Cuoi
76
21 22

Dau>Cuoi?
Giua  [ (Dau + Cuoi)/2 ]
Đưa ra Giua
rồi kết thúc
Sai
Đúng
Đúng
Sai
Đúng
N = 10 K = 25
Giua
Cuoi
76
21 22
Giua
Cuoi
Dau
Dau
CuoiDau
2221 30 31 33
76 8 9
10
76 8 9
10
54321i
A 2221 30 31 3396542
Giua
7
22
Cuoi