Trong quá trình tối ưu hóa truy vấn dữ liệu người dùng tại Unicode Academy, khi nào một lập trình viên Junior nên ưu tiên sử dụng thuật toán tìm kiếm nhị phân (Binary Search) thay vì tìm kiếm tuần tự (Linear Search), và độ phức tạp của nó là bao nhiêu?

Question

Accepted Answer

Tìm kiếm nhị phân (Binary Search) là thuật toán cực kỳ hiệu quả dựa trên tư tưởng Chia để trị (Divide and Conquer), với độ phức tạp thời gian là O(log N), trong khi tìm kiếm tuần tự (Linear Search) có độ phức tạp là O(N).
1. Bản chất cơ chế hoạt động

Điều kiện tiên quyết: Dữ liệu đầu vào bắt buộc phải được sắp xếp (Sorted array).
Cơ chế: Thuật toán chia đôi khoảng tìm kiếm liên tục, so sánh phần tử ở giữa với giá trị cần tìm. Nếu giá trị nhỏ hơn, tìm ở nửa bên trái; lớn hơn thì tìm ở nửa bên phải. Giảm số lượng phần tử cần xét đi một nửa sau mỗi bước.

2. Ví dụ minh họa thực chiến
Tìm kiếm mã khóa học trong danh sách đã sắp xếp:
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid; // Trả về vị trí
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1; // Không tìm thấy
}
3. Lưu ý kinh nghiệm thực chiến
Junior thường áp dụng Binary Search trực tiếp lên mảng chưa sắp xếp dẫn đến lỗi logic. Hơn nữa, việc sắp xếp mảng tốn O(N log N), do đó chỉ dùng Binary Search khi mảng đã được sắp xếp sẵn hoặc số lần tìm kiếm lặp lại rất nhiều lần để bù đắp chi phí sắp xếp ban đầu.

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