Khi thực hiện thuật toán tìm kiếm nhị phân (Binary Search) trên một mảng dữ liệu người dùng đã được sắp xếp, tại sao độ phức tạp thời gian lại là O(log N) và điều kiện tiên quyết nào về mặt cấu trúc dữ liệu nếu bị vi phạm sẽ làm hỏng hoàn toàn thuật toán?

Question

Accepted Answer

Phân tích bản chất cơ chế hoạt động
Tìm kiếm nhị phân là thuật toán kinh điển hoạt động theo tư tưởng chia để trị (Divide and Conquer). Thay vì duyệt qua từng phần tử như Linear Search (O(N)), thuật toán liên tục chia đôi khoảng tìm kiếm bằng cách so sánh phần tử ở giữa với giá trị cần tìm.
Đánh giá Big-O Time Complexity

Time Complexity: O(log N). Lý do là sau mỗi lần bước lặp, không gian tìm kiếm bị thu hẹp lại một nửa. Số lần lặp tối đa để tìm thấy phần tử trong tập hợp N phần tử chính là cơ số 2 của N (log2 N).
Space Complexity: O(1) nếu viết bằng vòng lặp (Iteration), hoặc O(log N) nếu viết bằng đệ quy (Recursion) do vùng nhớ Call Stack.

Điều kiện tiên quyết bắt buộc
Thuật toán này chỉ hoạt động chính xác khi và chỉ khi mảng đầu vào đã đượ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 dữ liệu chưa được sắp xếp, việc áp dụng Binary Search sẽ trả về kết quả sai lệch hoàn toàn.
Ví dụ minh họa và Tối ưu
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}
Lưu ý kinh nghiệm thực chiến
Junior thường hay quên mất chi phí sắp xếp ban đầu. Nếu mảng chưa được sắp xếp và phải gọi hàm sort trước khi tìm kiếm, tổng độ phức tạp thời gian sẽ bị chi phối bởi thuật toán sắp xếp (thường là O(N log N)), làm mất đi ý nghĩa tối ưu của Binary Search nếu chỉ tìm kiếm một lần duy nhất.

Phân tích bản chất cơ chế hoạt động

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 big-o notation liên quan cùng chủ đề