Tài liệu bai 4
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (744.78 KB, 15 trang )
3. Một số ví dụ về thuật toán
Ví dụ 3: Bài toán tìm kiếm
a)Tìm kiếm tuần tự
b)Tìm kiếm nhị phân
** Xác định bài toán :
•
Input :
–
Dãy A là dãy tăng gồm N số nguyên khác
nhau a
1
, a
2
, ..., a
N
và một số nguyên k
•
Output :
–
Chỉ số i mà a
i
= k hoặc thông báo không
tìm thấy k trong dãy A
**
**
Ý tưởng:
Ý tưởng:
thu hẹp phạm vi tìm kiếm bằng
thu 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
cách so sánh k với số hạng ở giữa dãy
a
1
, a
2
, …, a
[(1+N)/2]
, … a
N-1
, a
N
Nếu k < a
[(N+1)/2]
Nếu k > a
[(N+1)/2]
Tìm kiếm trong phạm vi này Tìm kiếm trong phạm vi này
< a
[(1+N)/2]
> a
[(1+N)/2]
Giua = [ (1 + N)/2]
Nếu k = a
Giua
thì thông báo chỉ số Giua
