Khái niệm
Tìm kiếm tuyến tính (linear search) duyệt qua từng phần tử của dãy theo thứ tự, so sánh với giá trị cần tìm cho đến khi tìm thấy hoặc duyệt hết. Đây là thuật toán tìm kiếm đơn giản nhất và hoạt động trên mọi loại dữ liệu — không cần sắp xếp trước.
- Độ phức tạp thời gian: O(n) — xấu nhất duyệt hết n phần tử
- Độ phức tạp không gian: O(1) — chỉ dùng vài biến
Sơ đồ luồng
graph TD;
A((Bắt đầu)) --> B[i = 0];
B --> C{i < n?};
C -- Sai --> F[Trả về -1\nKhông tìm thấy];
C -- Đúng --> D{arr-i == target?};
D -- Đúng --> E[Trả về i\nTìm thấy tại vị trí i];
D -- Sai --> G[i = i + 1];
G --> C;
E --> H((Kết thúc));
F --> H;
Cài đặt cơ bản
def linear_search(arr, target):
"""Trả về vị trí đầu tiên của target, hoặc -1 nếu không có."""
for i, val in enumerate(arr):
if val == target:
return i
return -1
numbers = [4, 2, 7, 1, 9, 3, 5]
print(linear_search(numbers, 9)) # 4
print(linear_search(numbers, 6)) # -1
Ví dụ nâng cao
Tìm tất cả vị trí xuất hiện
def find_all(arr, target):
"""Trả về danh sách tất cả vị trí chứa target."""
return [i for i, val in enumerate(arr) if val == target]
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
print(find_all(data, 1)) # [1, 3]
print(find_all(data, 5)) # [4, 8]
print(find_all(data, 7)) # []
Tìm kiếm theo điều kiện
def find_first_even(arr):
"""Tìm số chẵn đầu tiên trong danh sách."""
for i, val in enumerate(arr):
if val % 2 == 0:
return i, val
return None
data = [3, 7, 5, 4, 2, 8]
result = find_first_even(data)
if result:
i, val = result
print(f"Số chẵn đầu tiên: {val} tại vị trí {i}") # 4 tại vị trí 3
Bài tập luyện tập
Dễ — Tìm phần tử lớn nhất
Cho danh sách số nguyên, tìm giá trị lớn nhất (không dùng hàm max có sẵn).
def tim_max(arr):
if not arr:
return None
max_val = arr[0]
for x in arr[1:]:
if x > max_val:
max_val = x
return max_val
print(tim_max([3, 1, 4, 1, 5, 9, 2, 6])) # 9
print(tim_max([-5, -2, -8, -1])) # -1
Trung bình — Đếm phần tử thoả điều kiện
Cho danh sách số nguyên và hai số a, b. Đếm số phần tử nằm trong đoạn [a, b].
def dem_trong_doan(arr, a, b):
dem = 0
for x in arr:
if a <= x <= b:
dem += 1
return dem
data = [1, 5, 3, 8, 2, 7, 4, 6]
print(dem_trong_doan(data, 3, 6)) # 4 (các số: 5, 3, 4, 6)
print(dem_trong_doan(data, 1, 2)) # 2 (các số: 1, 2)
Khó hơn — Tìm hai phần tử có tổng bằng target (O(n²))
Bài toán cổ điển: tìm cặp phần tử có tổng bằng target. Đây là lời giải thô O(n²) — sẽ được tối ưu về O(n) trong bài Hai con trỏ.
def tim_cap_tong(arr, target):
n = len(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] + arr[j] == target:
return (arr[i], arr[j])
return None
data = [2, 7, 11, 15]
print(tim_cap_tong(data, 9)) # (2, 7)
print(tim_cap_tong(data, 10)) # None
Khi nào dùng tìm kiếm tuyến tính?
- Dữ liệu chưa được sắp xếp và không thể sắp xếp trước.
- Danh sách quá ngắn (n < 100) — tìm kiếm nhị phân không đáng cài.
- Tìm kiếm theo điều kiện phức tạp mà không thể dùng bảng tra.
- Khi chỉ cần tìm một lần duy nhất.
Nếu dữ liệu đã được sắp xếp và cần tìm kiếm nhiều lần, hãy dùng Tìm kiếm nhị phân — nhanh hơn đáng kể với n lớn.
Bình luận