Tìm kiếm tuyến tính và nhị phân: điều kiện dữ liệu quyết định thuật toán

🔎 Hai chiến lược, hai điều kiện

Tìm kiếm tuyến tính kiểm tra lần lượt nên dùng được với dữ liệu chưa sắp xếp; trường hợp xấu nhất cần n lần so sánh. Tìm kiếm nhị phân so với phần tử giữa rồi loại một nửa miền còn lại, nhưng cần dữ liệu đã sắp xếp theo cùng khóa.

Bất biến giúp tránh lỗi

Duy trì đoạn chỉ số [left,right] mà mục tiêu, nếu tồn tại, phải nằm trong đó. Tính mid, so sánh, rồi đặt left=mid+1 hoặc right=mid−1. Dừng khi tìm thấy hoặc left>right. Quy tắc cập nhật phải loại mid để vòng lặp tiến triển.

Độ phức tạp

• Tuyến tính: O(n) ở trường hợp xấu nhất.
• Nhị phân: O(log n), vì sau k bước còn khoảng n/2^k phần tử.

⚠️ Không quên chi phí chuẩn bị

Nếu chỉ tìm một lần trong dữ liệu nhỏ chưa sắp xếp, sắp xếp trước có thể không đáng. Nếu tìm nhiều lần và dữ liệu ít thay đổi, chi phí sắp xếp có thể được bù. Với phần tử trùng, thuật toán cơ bản chỉ bảo đảm tìm một vị trí, không mặc nhiên là vị trí đầu tiên.