1. Tìm kiếm Tuần tự (Linear Search)
Ý tưởng thuật toán
Thuật toán này hoạt động theo cách duyệt quét toàn bộ.
Bắt đầu từ phần tử đầu tiên của danh sách và so sánh trực tiếp với giá trị cần tìm.
+ Nếu không khớp, nhảy sang phần tử tiếp theo.
+ Quá trình này lặp lại cho đến khi tìm thấy mục tiêu hoặc đã kiểm tra hết mọi phần tử trong mảng mà không thấy.
Mã nguồn Python
def linear_search(arr, target): # Duyệt qua từng chỉ số i từ 0 đến n-1 for i in range(len(arr)): # So sánh phần tử hiện tại với mục tiêu if arr[i] == target: return i # Tìm thấy! Trả về vị trí return -1 # Duyệt hết mà không thấy # Cách dùng: data = [12, 45, 7, 23, 56] pos = linear_search(data, 23)
Minh họa các bước
2. Tìm kiếm Nhị phân (Binary Search)
Ý tưởng thuật toán
- Thuật toán này áp dụng chiến thuật Chia để trị (Divide and Conquer).
- Thay vì kiểm tra từng số, thuật toán luôn nhảy vào kiểm tra phần tử nằm giữa danh sách.
- Nhờ dữ liệu đã được sắp xếp, nếu giá trị ở giữa lớn hơn mục tiêu, ta biết chắc mục tiêu chỉ có thể nằm ở nửa bên trái và ngược lại.
- Mỗi lần so sánh, ta loại bỏ được 50% lượng dữ liệu còn lại, giúp tốc độ tìm kiếm cực nhanh.
Mã nguồn Python
def binary_search(arr, target): low = 0 high = len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] == target: return mid # Tìm thấy ở giữa elif arr[mid] < target: low = mid + 1 # Tìm nửa bên phải else: high = mid - 1 # Tìm nửa bên trái return -1 # Lưu ý: data PHẢI được sắp xếp trước data = [5, 12, 18, 23, 31, 45, 56] pos = binary_search(data, 12)
Minh họa các bước (Trace)
Chỉ mất 2 bước thay vì 6 bước như tìm tuần tự!
Độ phức tạp thuật toán
Linear Search
- • Tốt nhất: O(1)
- • Tệ nhất: O
- • Đặc điểm: Đơn giản, dùng cho dữ liệu chưa sắp xếp.
Binary Search
- • Tốt nhất: O(1)
- • Tệ nhất: O(log n)
- • Đặc điểm: Bắt buộc dữ liệu đã được sắp xếp.
