Tìm kiếm tuần tự và nhị phân: điều kiện đúng quan trọng hơn tốc độ

💻 Vì sao tìm kiếm nhị phân nhanh?

Tìm kiếm tuần tự kiểm tra từng phần tử nên 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 khoảng tìm kiếm, nên cần cỡ log₂n bước.

Nhị phân chỉ đúng khi dữ liệu có thứ tự phù hợp với phép so sánh.

Bất biến của tìm kiếm nhị phân

Nếu mục tiêu tồn tại, nó luôn nằm trong đoạn [left,right] đang xét. Với mid=floor((left+right)/2): nếu a[mid]<target thì left=mid+1; nếu lớn hơn thì right=mid−1.

⚠️ Dữ liệu chưa sắp xếp

Không được áp dụng nhị phân trực tiếp. Nếu chỉ tìm một lần, chi phí sắp xếp có thể lớn hơn lợi ích; nếu tìm nhiều lần, sắp xếp hoặc xây dựng chỉ mục có thể hợp lí.

🔎 Tránh lỗi biên

Ghi rõ đoạn đóng hay nửa mở, điều kiện vòng lặp và quy tắc cập nhật. Mỗi bước phải làm đoạn tìm kiếm nhỏ đi.

📚 Lý thuyết trọng tâm

Mục tiêu: Compare linear and binary search, state the sorted-data precondition and trace interval updates without off-by-one errors.. Khi học Tìm kiếm tuần tự và nhị phân: điều kiện đúng quan trọng hơn tốc độ, hãy xác định khái niệm, điều kiện áp dụng và mối liên hệ giữa các dữ kiện; không chỉ ghi nhớ kết luận.

🧭 Ví dụ có hướng dẫn

Chọn một tình huống điển hình của bài. Bước 1: ghi dữ kiện và câu hỏi cần giải quyết. Bước 2: chọn khái niệm hoặc quy tắc phù hợp. Bước 3: giải thích từng bước và kiểm tra kết quả với điều kiện ban đầu. Nếu đổi một dữ kiện, hãy dự đoán kết quả thay đổi thế nào.

✍️ Luyện tập

Tóm tắt bài bằng ba ý: khái niệm, điều kiện và kết luận.
Tự tạo một ví dụ đúng và một phản ví dụ; chỉ ra điểm quyết định.
Giải lại ví dụ khi thay đổi một dữ kiện, sau đó nêu cách kiểm chứng.

Checklist tự đánh giá

Tôi giải thích được “vì sao”, không chỉ nêu đáp án.
Tôi nhận ra trường hợp không áp dụng được quy tắc.
Tôi kiểm tra được đơn vị, bằng chứng hoặc tính hợp lí của kết luận.