Binary Search

Bài toán

Cho một mảng các số nguyên nums đã được sắp xếp tăng dần, và một số nguyên target. Viết hàm tìm target trong nums. Nếu tồn tại trả về index, nếu không trả về -1. Yêu cầu thuật toán phải có độ phức tạp thời gian O(log n).

Ví dụ:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Giải thích: 9 xuất hiện tại vị trí index 4.

Phân Tích & Tiếp Cận

Tại sao không dùng for loop (O(n))?

Đề bài yêu cầu $O(\log n)$. Duyệt mảng tuần tự là $O(n)$, quá chậm. Vì mảng đã sắp xếp, ta có thể dùng phương pháp "Chia để trị" (Divide and Conquer).

Thuật toán Tìm kiếm nhị phân

Ý tưởng giống như tra từ điển:

1. Mở trang giữa cuốn từ điển.
2. Nếu từ cần tìm nằm ở nửa trước -> Vứt bỏ nửa sau. Tím kiếm tiếp trong nửa trước.
3. Nếu từ cần tìm nằm ở nửa sau -> Vứt bỏ nửa trước. Tìm kiếm tiếp trong nửa sau.
4. Lặp lại cho đến khi tìm thấy hoặc hết trang.

Cài đặt

Ta dùng 2 con trỏ left và right để giới hạn phạm vi tìm kiếm. Phạm vi hiện tại: [left, right]. Điểm giữa: mid = left + Math.floor((right - left) / 2). (Dùng công thức này thay vì (left+right)/2 để tránh tràn số int trong một số ngôn ngữ cấp thấp, dù JS không bị nhưng là thói quen tốt).

• Nếu nums[mid] == target: Tìm thấy!
• Nếu nums[mid] < target: Target nằm bên phải -> left = mid + 1.
• Nếu nums[mid] > target: Target nằm bên trái -> right = mid - 1.

function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        // Tính điểm giữa
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            // Loại bỏ nửa bên trái, tìm ở bên phải
            left = mid + 1;
        } else {
            // Loại bỏ nửa bên phải, tìm ở bên trái
            right = mid - 1;
        }
    }

    return -1;
}

• Time Complexity: $O(\log n)$. Vì sau mỗi bước, không gian tìm kiếm chia đôi. $N \rightarrow N/2 \rightarrow N/4 \rightarrow ... \rightarrow 1$.
• Space Complexity: $O(1)$.

Pattern Nhận Diện

Khi đề bài có cụm từ "Sorted Array" (Mảng đã sắp xếp) và yêu cầu độ phức tạp $O(\log n)$, 99% đó là Binary Search. Lưu ý điều kiện vòng lặp while (left <= right) (có dấu bằng) là nguồn gốc của nhiều lỗi "Off-by-one". Hãy chạy thử vối mảng 1 phần tử [5] để kiểm chứng logic.