Chúc Mừng Năm Mới!

Chào mừng các bạn đến với bài viết đầu tiên của mình trong năm Giáp Thìn! Nhân dịp năm mới, mình muốn chia sẻ một chút kiến thức về thuật toán mà nhiều bạn thường gặp khi đi phỏng vấn tại các công ty công nghệ.

Hy vọng mỗi khởi đầu đều thuận lợi, chúc mọi người trong năm mới Giáp Thìn đạt được nhiều thành công trong việc chinh phục các bài phỏng vấn!

Giới Thiệu Về Thuật Toán Binary Search

Gần đây, mình đã tham gia luyện tập trên LeetCode để tìm niềm vui sau những giờ làm việc căng thẳng. Trong quá trình luyện tập, mình đã gặp phải một số bài toán yêu cầu sử dụng thuật toán Binary Search. Nếu bạn chưa biết, Binary Search là thuật toán tìm kiếm một giá trị target trong một mảng đã sắp xếp. Thuật toán này hoạt động qua các bước sau:

1. So sánh giá trị target với phần tử chính giữa của mảng (middle).
2. Nếu target không bằng middle, ta sẽ tìm kiếm trong nửa mảng có giá trị nhỏ hơn hoặc lớn hơn middle, tùy theo điều kiện bài toán.
3. Quá trình này lặp lại cho đến khi tìm thấy vị trí của phần tử bằng với target.

Vì mỗi bước tìm kiếm giảm số lượng phần tử còn lại một nửa, nên độ phức tạp của thuật toán này là O(log n).

Mặc dù thuật toán có vẻ dễ hiểu, nhưng để áp dụng chính xác, bạn cần chú ý nhiều điều sau:

• Khi nào nên dừng vòng lặp? Sử dụng left < right hay left <= right?
• Cách cập nhật các giá trị biên như thế nào? Dùng left = mid hay left = mid + 1? Kiểm soát sai lầm trong các quyết định này có thể dẫn đến kết quả sai lệch và tiêu tốn nhiều thời gian.

Template Giải Quyết Vấn Đề Binary Search

Tới đây, mình xin giới thiệu một template đơn giản nhưng mạnh mẽ mà mình đã tìm ra:

int binarySearch() {
    int left = min(searchSpace), right = max(searchSpace);
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (condition(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

boolean condition(int num) {
    // Implement the condition logic here
}

Các bước áp dụng template này:

1. Tìm giá trị left và right phù hợp, đảm bảo tính bao trùm toàn bộ giá trị có thể là kết quả bài toán.
2. Định nghĩa chính xác hàm condition, đây thường là phần khó khăn nhất trong các bài toán Binary Search phức tạp.
3. Chọn giá trị trả về là left hay left - 1 tùy thuộc vào yêu cầu bài toán.

Ví Dụ Cụ Thể

Bài Toán Đơn Giản: Tìm Căn Bậc 2

Cho số nguyên không âm x, tìm căn bậc 2 của x, làm tròn xuống số nguyên gần nhất. Ví dụ:

• Input: 4, Output: 2
• Input: 8, Output: 2

Hàm condition có thể được viết như sau:

boolean condition(int num) {
    return x / num < num;
}

Và khi kết thúc vòng lặp, giá trị cần tìm sẽ là left - 1.

public int mySqrt(int x) {
    if (x < 2) return x;
    int left = 0;
    int right = x;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (x / mid < mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left - 1;
}

Bài Toán Phức Tạp: Gói Hàng Chuyển Trong D Ngày

Cũng với mẫu Binary Search, hãy xem xét vấn đề giao gói hàng trong vòng D ngày:

• Input: mảng khối lượng weights, tìm tải trọng tối thiểu của khay hàng.
• Điều kiện: 1 <= D <= weights.length <= 5 * 10^4

Để giải bài toán này, ta sẽ xác định hai biên: tải trọng tối thiểu và tối đa, sau đó áp dụng phương pháp Binary Search:

public int shipWithinDays(int[] weights, int days) {
    int left = 0;
    int right = 0;
    for (int w : weights) {
        left = Math.max(left, w);
        right += w;
    }
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isValidTime(weights, days, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

private boolean isValidTime(int[] weights, int days, int capacity) {
    int totalDay = 1;
    int curCap = 0;
    for (int w : weights) {
        curCap += w;
        if (curCap > capacity) {
            totalDay++;
            curCap = w;
        }
    }
    return totalDay <= days;
}

Kết Luận

Mong rằng bài viết này sẽ giúp các bạn tự tin thêm trong việc chinh phục các bài toán trên LeetCode. Đừng quên rằng, nếu nhận biết bài toán có thể áp dụng Binary Search, bạn có thể dễ dàng sử dụng template này và tiến đến giải quyết bài toán một cách hiệu quả!

🔔 Đọc thêm trên blog: henrytechie.com
☕️ Kết nối với mình trên Facebook: Henry Techie
☁️ Theo dõi TikTok của mình: @henrytechie
source: viblo