Trả lời nhanh
Thuật toán tìm kiếm tuần tự giải bài toán: cho một dãy và một giá trị khoá, hãy cho biết khoá có trong dãy hay không và ở vị trí nào. Cách làm là so sánh khoá lần lượt với từng phần tử, bắt đầu từ phần tử đầu tiên. Gặp phần tử bằng khoá thì dừng và báo vị trí. Duyệt hết dãy mà không gặp thì kết luận không có.
Bài toán mà tìm kiếm tuần tự giải quyết
Hình dung bạn có một dãy số hoặc danh sách tên chưa sắp xếp, và cần biết một giá trị nào đó có nằm trong đó không. Đây là bài toán tìm kiếm.
- Input (đầu vào): dãy A gồm N phần tử và một giá trị khoá k cần tìm.
- Output (đầu ra): vị trí của phần tử đầu tiên bằng k, hoặc thông báo “không tìm thấy”.
Tìm kiếm tuần tự (còn gọi là tìm kiếm tuyến tính) là cách đơn giản nhất: làm đúng như người tìm một cuốn sách trên giá, nhìn từng cuốn từ đầu giá cho đến khi thấy.
Các bước thực hiện
- Gán i ← 1 (xét phần tử đầu tiên).
- Nếu A[i] = k thì kết luận “tìm thấy ở vị trí i” và kết thúc.
- Nếu chưa bằng thì tăng i lên 1.
- Nếu i > N thì kết luận “không có k trong dãy” và kết thúc; ngược lại quay lại bước 2.
Hai điều kiện dừng cần nhớ: tìm thấy hoặc hết dãy. Thiếu điều kiện thứ hai, thuật toán sẽ “chạy lố” ra ngoài dãy.
Ví dụ minh hoạ
Cho dãy A = (7, 3, 9, 5, 1), N = 5.
| Khoá k | Quá trình so sánh | Kết quả | Số lần so sánh |
|---|---|---|---|
| 9 | 7≠9, 3≠9, 9=9 | Tìm thấy ở vị trí 3 | 3 |
| 7 | 7=7 | Tìm thấy ở vị trí 1 | 1 |
| 8 | so với cả 5 phần tử đều khác | Không tìm thấy | 5 |
Cài đặt bằng Python
def tim_tuan_tu(a, k):
for i in range(len(a)):
if a[i] == k:
return i # vị trí tính từ 0
return -1 # không tìm thấy
print(tim_tuan_tu([7, 3, 9, 5, 1], 9)) # in ra 2Lưu ý: Python đánh chỉ số từ 0 nên phần tử thứ 3 có chỉ số 2. Đây là chỗ học sinh hay nhầm khi đối chiếu với cách đếm từ 1 ở phần mô tả thuật toán.
Đánh giá: nhanh hay chậm?
- Tốt nhất: khoá nằm ở đầu dãy, chỉ 1 lần so sánh.
- Xấu nhất: khoá ở cuối dãy hoặc không có, cần N lần so sánh.
- Ưu điểm: dễ viết, dãy không cần sắp xếp trước.
- Nhược điểm: dãy rất dài thì chậm, vì số bước tăng tỉ lệ với N.
Nếu dãy đã được sắp xếp, ta có thể dùng tìm kiếm nhị phân để nhanh hơn nhiều. Nhưng khi dãy chưa sắp xếp, tìm kiếm tuần tự là lựa chọn hợp lý.
Lỗi sai thường gặp
- Nhầm với sắp xếp: tìm kiếm tuần tự không thay đổi thứ tự các phần tử.
- Cho rằng phải duyệt hết dãy mới kết luận. Thực tế gặp khoá là dừng ngay.
- Quên trường hợp không tìm thấy, không trả về giá trị báo hiệu (như −1).
- Nhầm “tuần tự” với “từ nhỏ đến lớn”. Tuần tự ở đây là theo thứ tự vị trí.
Bài luyện tập
Bài 1. Cho dãy (4, 8, 2, 8, 6). Tìm k = 8 bằng tìm kiếm tuần tự (dừng khi gặp lần đầu). Cho biết vị trí (đếm từ 1) và số lần so sánh.
Đáp án: vị trí 2, sau 2 lần so sánh (4≠8, 8=8).
Bài 2. Dãy có 10 phần tử không chứa khoá k. Thuật toán so sánh bao nhiêu lần?
Đáp án: 10 lần, vì phải duyệt hết dãy mới kết luận không có.
Bài 3. Muốn liệt kê tất cả vị trí của k = 8 trong dãy ở Bài 1 thì phải sửa thuật toán thế nào?
Đáp án: không dừng khi gặp mà tiếp tục duyệt đến hết dãy, ghi lại mọi vị trí có A[i] = 8. Kết quả là các vị trí 2 và 4, sau 5 lần so sánh.
Ghi nhớ
Tìm kiếm tuần tự = duyệt từ đầu, so sánh từng phần tử với khoá, gặp thì dừng, hết dãy thì báo không có.
Câu hỏi thường gặp
Thuật toán tìm kiếm tuần tự thực hiện công việc gì?
Tìm xem một giá trị (khoá) có trong dãy hay không và ở vị trí nào, bằng cách so sánh khoá lần lượt với từng phần tử từ đầu dãy.
Tìm kiếm tuần tự có cần dãy được sắp xếp trước không?
Không. Thuật toán hoạt động với dãy bất kỳ vì nó xét từng phần tử một theo thứ tự vị trí.
Trong trường hợp xấu nhất, tìm kiếm tuần tự so sánh bao nhiêu lần?
N lần với dãy N phần tử, khi khoá nằm ở cuối dãy hoặc không có trong dãy.
Khi nào thuật toán tìm kiếm tuần tự dừng?
Dừng khi gặp phần tử bằng khoá (tìm thấy) hoặc khi đã xét hết các phần tử mà không gặp (không tìm thấy).