Trong bài toán tìm kiếm trên mảng đã sắp xếp, tại sao việc sử dụng Binary Search lại giúp giảm độ phức tạp thời gian từ O(n) xuống O(log n) và giới hạn của thuật toán này là gì?

Question

Accepted Answer

Bản chất cơ chế
Binary Search hoạt động dựa trên nguyên lý chia để trị (Divide and Conquer). Bằng cách so sánh giá trị cần tìm với phần tử ở giữa (mid), thuật toán có thể loại bỏ ngay lập tức một nửa không gian tìm kiếm trong mỗi bước lặp.
Tại sao đạt O(log n)?
Với mỗi bước, kích thước không gian tìm kiếm giảm đi một nửa: n -> n/2 -> n/4 -> ... -> 1. Số lần chia tối đa để đạt đến 1 phần tử là log2(n).
Giới hạn thực chiến

Yêu cầu tiên quyết: Dữ liệu bắt buộc phải được sắp xếp (Sorted).
Truy cập ngẫu nhiên: Chỉ hiệu quả trên các cấu trúc hỗ trợ truy cập ngẫu nhiên (như Array). Trên Linked List, độ phức tạp vẫn là O(n) do không thể nhảy đến phần tử giữa ngay lập tức.
Chi phí sắp xếp: Nếu dữ liệu thường xuyên thay đổi, chi phí duy trì trạng thái sắp xếp có thể lớn hơn lợi ích tìm kiếm mang lại.

Trong bài toán tìm kiếm trên mảng đã sắp xếp, tại sao việc sử dụng Binary Search lại giúp giảm độ phức tạp thời gian từ O(n) xuống O(log n) và giới hạn của thuật toán này là gì?

Bản chất cơ chế

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ủ đề