Thuật toán Binary Search là gì? Giải thích dễ hiểu kèm demo trực quan

Thuật toán Binary Search là gì? Giải thích dễ hiểu kèm demo trực quan

Binary Search (tìm kiếm nhị phân) là một trong những thuật toán tìm kiếm hiệu quả nhất trên mảng đã được sắp xếp. Thay vì duyệt lần lượt từng phần tử như Linear Search, Binary Search luôn “chẻ đôi” không gian tìm kiếm sau mỗi bước.

Nhờ đó, độ phức tạp thời gian chỉ còn O(log n), cực kỳ hiệu quả với dữ liệu lớn.

Binary Search giải bài toán gì?

• Tìm vị trí của một phần tử trong mảng đã sắp xếp (thường là tăng dần).
• Kiểm tra một giá trị có tồn tại trong tập dữ liệu đã sắp xếp hay không.
• Dùng nhiều trong các bài toán cần tìm ngưỡng, tìm vị trí biên, lower_bound, upper_bound, v.v.

Điều kiện để dùng Binary Search

• Dữ liệu phải được sắp xếp theo một thứ tự cố định (tăng dần hoặc giảm dần).
• Phải truy cập được phần tử theo chỉ số (array, random access).

Ý tưởng chính của thuật toán Binary Search

Giả sử mảng tăng dần, ta có các bước:

1. Đặt hai biến left (trái) và right (phải) lần lượt là 0 và n - 1.
2. Tính mid = (left + right) / 2 (lấy phần nguyên).
3. So sánh arr[mid] với key cần tìm:
   • Nếu arr[mid] == key → tìm thấy.
   • Nếu arr[mid] < key → loại bỏ nửa trái, đặt left = mid + 1.
   • Nếu arr[mid] > key → loại bỏ nửa phải, đặt right = mid - 1.
4. Lặp lại cho đến khi left > right → không tìm thấy.

Ví dụ minh họa

Mảng (đã sắp xếp): [2, 3, 4, 5, 7, 8]
Key tìm: 5

Bước 1:
left = 0, right = 5 → mid = 2 → arr[2] = 4 < 5
→ bỏ nửa trái, chỉ giữ [5, 7, 8] → left = 3, right = 5

Bước 2:
mid = (3 + 5) / 2 = 4 → arr[4] = 7 > 5
→ bỏ nửa phải của đoạn này, giữ [5] → left = 3, right = 3

Bước 3:
mid = 3 → arr[3] = 5 == key → tìm thấy tại index 3

Demo Binary Search bằng JavaScript

Demo dưới đây minh họa trực quan cách Binary Search hoạt động trên mảng đã sắp xếp [2, 3, 4, 5, 7, 8]:

• Highlight đoạn đang được xét (left → right).
• Highlight riêng phần tử mid.
• Log từng bước so sánh và thu hẹp phạm vi.
• Thông báo rõ ràng khi tìm thấy hoặc không tìm thấy.

Phân tích code Binary Search

1. Ghi lại từng bước chạy

function binarySearchWithSteps(arr, key) {
    var steps = [];
    var left = 0;
    var right = arr.length - 1;

    while (left <= right) {
        var mid = Math.floor((left + right) / 2);
        var midVal = arr[mid];

        steps.push({
            type: "check",
            left: left,
            right: right,
            mid: mid,
            midValue: midVal
        });

        if (midVal === key) {
            steps.push({
                type: "found",
                left: left,
                right: right,
                mid: mid,
                midValue: midVal
            });
            return steps;
        } else if (midVal < key) {
            steps.push({
                type: "move_right",
                left: left,
                right: right,
                mid: mid,
                midValue: midVal
            });
            left = mid + 1;
        } else {
            steps.push({
                type: "move_left",
                left: left,
                right: right,
                mid: mid,
                midValue: midVal
            });
            right = mid - 1;
        }
    }

    steps.push({ type: "not_found" });
    return steps;
}

2. Hiển thị mảng & highlight left – right – mid

function renderBinaryArray(container, arr, opts) {
    opts = opts || {};
    var left = opts.left;
    var right = opts.right;
    var mid = opts.mid;
    var found = opts.found;

    container.innerHTML = "";

    arr.forEach(function(value, index) {
        var div = document.createElement("div");
        div.className = "bin-cell";

        if (left != null && right != null && index >= left && index <= right) {
            div.classList.add("bin-range");
        }

        if (index === mid) {
            div.classList.add("bin-mid");
        }

        if (index === found) {
            div.classList.add("bin-found");
        }

        div.textContent = value;
        container.appendChild(div);
    });
}

3. Chạy animation từng bước

function playBinarySteps(steps, arr) {
    var index = 0;
    binaryLog.innerHTML = "";
    binaryResult.textContent = "Đang chạy Binary Search...";

    function next() {
        if (index >= steps.length) return;

        var step = steps[index];
        var msg = "";
        var opts = {};

        if (step.type === "check") {
            msg =
                "Xét mid = " +
                step.mid +
                " (giá trị " +
                step.midValue +
                "), đoạn hiện tại: [" +
                step.left +
                ", " +
                step.right +
                "].";
            opts.left = step.left;
            opts.right = step.right;
            opts.mid = step.mid;
        } else if (step.type === "move_right") {
            msg =
                "Vì midValue = " +
                step.midValue +
                " < key, bỏ nửa trái, giữ đoạn bên phải.";
            opts.left = step.mid + 1;
            opts.right = step.right;
            opts.mid = null;
        } else if (step.type === "move_left") {
            msg =
                "Vì midValue = " +
                step.midValue +
                " > key, bỏ nửa phải, giữ đoạn bên trái.";
            opts.left = step.left;
            opts.right = step.mid - 1;
            opts.mid = null;
        } else if (step.type === "found") {
            msg =
                "Tìm thấy key tại mid = " +
                step.mid +
                " (giá trị " +
                step.midValue +
                ").";
            opts.left = step.left;
            opts.right = step.right;
            opts.mid = step.mid;
            opts.found = step.mid;

            renderBinaryArray(binaryArray, arr, opts);
            var p = document.createElement("p");
            p.innerHTML = msg;
            binaryLog.appendChild(p);
            binaryLog.scrollTop = binaryLog.scrollHeight;

            binaryResult.innerHTML =
                'Tìm thấy tại index <strong>' + step.mid + '</strong> (giá trị = ' + step.midValue + ')';
            return;
        } else if (step.type === "not_found") {
            msg = "Không tìm thấy key trong mảng.";
            renderBinaryArray(binaryArray, arr, {});
            var pEnd = document.createElement("p");
            pEnd.innerHTML = msg;
            binaryLog.appendChild(pEnd);
            binaryLog.scrollTop = binaryLog.scrollHeight;
            binaryResult.innerHTML = "<strong>Không tồn tại trong mảng.</strong>";
            return;
        }

        renderBinaryArray(binaryArray, arr, opts);

        var p = document.createElement("p");
        p.innerHTML = msg;
        binaryLog.appendChild(p);
        binaryLog.scrollTop = binaryLog.scrollHeight;

        index++;
        setTimeout(next, 700);
    }

    next();
}

Khi nào nên dùng Binary Search?

• Khi dữ liệu đã được sắp xếp.
• Khi kích thước dữ liệu lớn và cần tốc độ tìm kiếm tốt.
• Khi có thể chấp nhận chi phí sắp xếp trước (hoặc dữ liệu vốn dĩ luôn có thứ tự).

Kết luận

Binary Search là “vũ khí cơ bản” để tối ưu các thao tác tìm kiếm trên dữ liệu đã sắp xếp. Việc hiểu rõ cách nó thu hẹp phạm vi sau mỗi lần so sánh sẽ giúp bạn dễ dàng áp dụng vào hàng loạt bài toán từ đơn giản đến nâng cao.

Với demo trực quan trên, từng bước tính mid, so sánh và thu hẹp đoạn [left, right] được thể hiện rõ, giúp việc học và ghi nhớ trở nên rất “mượt”.