Trong bài toán tìm kiếm phần tử trong mảng, tại sao việc sử dụng thuật toán Binary Search trên một mảng chưa được sắp xếp lại là một sai lầm nghiêm trọng và hệ quả của nó là gì?

Question

Accepted Answer

Bản chất vấn đề
Thuật toán Binary Search hoạt động dựa trên nguyên lý chia để trị (divide and conquer), yêu cầu tiên quyết là dữ liệu đầu vào phải được sắp xếp theo một thứ tự nhất định (tăng dần hoặc giảm dần). Nếu áp dụng trên mảng chưa sắp xếp, thuật toán sẽ không thể xác định được nửa nào của mảng chứa giá trị cần tìm.
Hệ quả

Sai lệch kết quả: Thuật toán sẽ trả về kết quả sai hoặc không tìm thấy phần tử dù nó tồn tại trong mảng.
Lãng phí tài nguyên: Việc cố gắng sắp xếp mảng ngay trước khi tìm kiếm (ví dụ dùng QuickSort) sẽ làm tăng độ phức tạp thời gian từ O(log n) lên O(n log n), gây chậm hệ thống.

Giải pháp

Nếu dữ liệu thay đổi liên tục: Sử dụng Linear Search với độ phức tạp O(n).
Nếu cần tìm kiếm nhiều lần trên tập dữ liệu tĩnh: Hãy thực hiện sắp xếp một lần duy nhất trước khi bắt đầu chuỗi các thao tác tìm kiếm bằng Binary Search.

Trong bài toán tìm kiếm phần tử trong mảng, tại sao việc sử dụng thuật toán Binary Search trên một mảng chưa được sắp xếp lại là một sai lầm nghiêm trọng và hệ quả của nó là gì?

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi searching liên quan cùng chủ đề