Tìm thấy thì dừng, không thấy thì duyệt hết
Tìm kiếm tuần tự xem từng phần tử từ trái sang phải. Nếu phần tử đang xem bằng giá trị cần tìm, hàm trả ngay chỉ số của nó. Nếu duyệt hết vẫn không thấy, hàm trả `-1`. Với dãy dài `n`, trường hợp xấu nhất phải so sánh `n` phần tử; vì vậy bậc thời gian là `O(n)`. Trường hợp tìm thấy ở đầu chỉ cần một lần so sánh khi dãy không rỗng. Dãy rỗng không cần so sánh phần tử nào.
Kiểm số lần so sánh bằng mã
Hàm sau trả cả chỉ số và số phép so sánh `a[i] == x`:
```python
def tim_tuan_tu_va_dem(a, x):
so_sanh = 0
for i in range(len(a)):
so_sanh += 1
if a[i] == x:
return i, so_sanh
return -1, so_sanh
a = [7, 4, 9, 4]
print(tim_tuan_tu_va_dem(a, 7))
print(tim_tuan_tu_va_dem(a, 4))
print(tim_tuan_tu_va_dem(a, 8))
```
Ba dòng kết quả là `(0, 1)`, `(1, 2)` và `(-1, 4)`. Giá trị 4 xuất hiện hai lần nhưng hàm trả **vị trí đầu tiên**. Nếu `a = []`, hàm trả `(-1, 0)`. Số đếm là số phép so sánh cụ thể trong mã này, không phải tổng mọi thao tác máy.
Bài luyện
Với `a = [7, 4, 9, 4]`, `tim_tuan_tu_va_dem(a, 4)` trả gì?
Gặp 4 đầu tiên ở chỉ số 1 sau hai phép so sánh.
Hàm dừng trước khi tới 4 thứ hai.
4 có trong dãy.
4 là giá trị, không phải chỉ số trả về.
Lời giải
So sánh 7 rồi 4; lần thứ hai đã thấy tại chỉ số 1, nên trả (1, 2).
Bài luyện
Với dãy `n` phần tử không chứa `x`, phép `a[i] == x` chạy bao nhiêu lần?
Hàm vẫn duyệt dãy nếu n>0.
Chỉ một lần khi n=1.
Mỗi phần tử được so sánh một lần.
Không có hai vòng lồng nhau.
Lời giải
Không thấy x nên vòng lặp đi qua đủ n phần tử, mỗi phần tử một phép so sánh.
Bài luyện
Bậc thời gian trường hợp xấu nhất của tìm kiếm tuần tự theo độ dài dãy `n` là gì?
Chỉ đúng cho trường hợp tìm thấy ngay đầu.
Không chia đôi phạm vi tìm kiếm.
Tối đa n phép so sánh và thêm thao tác hằng số.
Mã chỉ có một vòng duyệt.
Lời giải
Khi phần tử ở cuối hoặc không có, hàm so sánh n lần; bậc xấu nhất là O(n).
Đang học