Trả lời nhanh
Thuật toán tìm kiếm tuần tự dùng để kiểm tra một giá trị cho trước (gọi là khoá) có xuất hiện trong một dãy hay không và nếu có thì cho biết vị trí của nó. Thuật toán làm việc bằng cách so sánh khoá với lần lượt từng phần tử, bắt đầu từ phần tử đầu tiên, cho đến khi gặp phần tử bằng khoá hoặc hết dãy mà không thấy.
Bài toán mà tìm kiếm tuần tự giải quyết
Bài toán tìm kiếm có dạng: cho một dãy gồm n phần tử a1, a2, …, an và một giá trị k. Hãy cho biết k có nằm trong dãy hay không; nếu có thì k ở vị trí nào.
- Đầu vào (Input): dãy a và khoá k.
- Đầu ra (Output): vị trí i sao cho ai = k, hoặc thông báo “không tìm thấy”.
Ví dụ đời thường: bạn lật từng trang vở từ trang đầu để tìm bài kiểm tra có điểm 10, hay dò từng tên trong danh sách lớp để tìm tên mình. Đó chính là tìm kiếm tuần tự.
Các bước của thuật toán
- Bước 1: Nhập dãy a và khoá k; đặt i ← 1.
- Bước 2: Nếu i > n thì thông báo “không tìm thấy” và kết thúc.
- Bước 3: Nếu ai = k thì thông báo vị trí i và kết thúc.
- Bước 4: Tăng i thêm 1 rồi quay lại Bước 2.
Thuật toán luôn dừng sau nhiều nhất n lần so sánh vì chỉ số i tăng dần và vượt n ở một thời điểm nào đó.
Ví dụ minh hoạ
Cho dãy A = (4, 7, 2, 9, 5) và khoá k = 9 (ví dụ tự đặt). Ta so sánh lần lượt:
| Lần so sánh | i | ai | ai = 9? |
|---|---|---|---|
| 1 | 1 | 4 | Sai, tăng i |
| 2 | 2 | 7 | Sai, tăng i |
| 3 | 3 | 2 | Sai, tăng i |
| 4 | 4 | 9 | Đúng, dừng, kết quả i = 4 |
Phần tử thứ 5 không cần xét nữa vì đã tìm thấy.
Cài đặt bằng Python
def tim_tuan_tu(a, k):
for i in range(len(a)):
if a[i] == k:
return i # chỉ số tính từ 0
return -1 # không tìm thấyLưu ý: Python đánh chỉ số từ 0 nên với ví dụ trên hàm trả về 3, tương ứng vị trí thứ 4 theo cách đếm từ 1.
Đánh giá số lần so sánh
| Trường hợp | Số lần so sánh |
|---|---|
| Tốt nhất (khoá ở đầu dãy) | 1 |
| Xấu nhất (khoá ở cuối dãy hoặc không có) | n |
| Trung bình (nếu khoá có trong dãy) | khoảng n/2 |
Ưu điểm: đơn giản, dễ cài đặt, không đòi hỏi dãy phải được sắp xếp. Nhược điểm: dãy càng dài thì càng chậm. Với dãy đã sắp xếp, tìm kiếm nhị phân thường nhanh hơn nhiều.
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ử, chỉ tìm giá trị.
- Cho rằng dãy phải sắp xếp trước: sai, điều kiện này chỉ cần với tìm kiếm nhị phân.
- Quên điều kiện dừng khi hết dãy: dễ gây lỗi vượt quá chỉ số hoặc lặp vô hạn.
- Báo “không tìm thấy” quá sớm: chỉ được kết luận sau khi đã so sánh khoá với tất cả phần tử.
Mẹo nhớ: “tuần tự” nghĩa là lần lượt từng cái một, đúng thứ tự, không nhảy cóc.
Bài luyện tập
- Cho dãy (15, 3, 8, 3, 20), khoá k = 3. Thuật toán cho kết quả vị trí nào và cần mấy lần so sánh?
Đáp án: dừng ở vị trí 2 (lần gặp đầu tiên), sau 2 lần so sánh. - Cho dãy 6 phần tử không chứa giá trị 50. Tìm k = 50 cần bao nhiêu lần so sánh?
Đáp án: 6 lần, rồi báo “không tìm thấy”. - Muốn tìm tất cả vị trí của k = 3 trong dãy ở câu 1, cần sửa thuật toán thế nào?
Đáp án: không dừng khi gặp, mà duyệt hết dãy và ghi lại mọi vị trí có ai = 3; kết quả là các vị trí 2 và 4.
Câu hỏi thường gặp
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 chỉ so sánh khoá với từng phần tử theo thứ tự nên dãy có thứ tự bất kỳ vẫn tìm được.
Số lần so sánh nhiều nhất của tìm kiếm tuần tự là bao nhiêu?
Nhiều nhất là n lần với dãy n phần tử, xảy ra 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ự kết thúc?
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 thấy (không tìm thấy).
Tìm kiếm tuần tự khác tìm kiếm nhị phân ở điểm nào?
Tìm kiếm tuần tự xét từng phần tử và không yêu cầu sắp xếp. Tìm kiếm nhị phân chia đôi phạm vi tìm và chỉ dùng được với dãy đã sắp xếp, nên thường nhanh hơn.