Bài 1.3. Vòng lặp nhị phân và ứng dụng trong các bài toán tìm kiếm

Chào mừng bạn trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Sau khi đã tìm hiểu về những khái niệm cơ bản, hôm nay chúng ta sẽ đi sâu vào một trong những thuật toán kinh điển và vô cùng hiệu quả cho các bài toán tìm kiếm: Tìm kiếm nhị phân (Binary Search), hay còn được gọi một cách hình ảnh là "vòng lặp nhị phân" vì cách nó lặp đi lặp lại quá trình chia đôi tập dữ liệu.

Bạn đã bao giờ cần tìm một cuốn sách trong một thư viện khổng lồ chưa? Nếu chúng được sắp xếp theo tên, bạn sẽ không cần phải xem xét từng cuốn một từ đầu đến cuối đúng không? Bạn chỉ cần mở ở giữa, xem tên cuốn sách đó thuộc nửa đầu hay nửa sau, rồi tiếp tục mở ở giữa phần còn lại... Đó chính là ý tưởng cốt lõi đằng sau Tìm kiếm nhị phân!

Tại sao cần Tìm kiếm nhị phân?

Hãy tưởng tượng bạn có một danh sách hàng triệu (hoặc thậm chí tỷ!) phần tử và cần kiểm tra xem một phần tử cụ thể có tồn tại trong danh sách đó hay không, hoặc tìm vị trí của nó.

Cách đơn giản nhất là Tìm kiếm tuyến tính (Linear Search): đi qua từng phần tử một, từ đầu đến cuối, cho đến khi tìm thấy hoặc hết danh sách. Thuật toán này hoạt động luôn đúng, nhưng lại cực kỳ kém hiệu quả với dữ liệu lớn. Trong trường hợp xấu nhất (phần tử ở cuối hoặc không có), bạn phải duyệt qua toàn bộ n phần tử. Độ phức tạp thời gian của nó là O(n).

Với dữ liệu khổng lồ, O(n) là một con số khủng khiếp. Chúng ta cần một phương pháp nhanh hơn đáng kể. Và đó là lúc Tìm kiếm nhị phân tỏa sáng!

Tìm kiếm nhị phân hoạt động như thế nào?

Điểm mấu chốt làm nên sức mạnh của Tìm kiếm nhị phân là nó chỉ hoạt động trên dữ liệu đã được sắp xếp. Nếu dữ liệu của bạn chưa được sắp xếp, bạn cần phải sắp xếp nó trước (chi phí sắp xếp thường là O(n log n) hoặc O(n²), nhưng chỉ làm một lần).

Giả sử chúng ta có một mảng arr đã được sắp xếp tăng dần và chúng ta muốn tìm một giá trị target.

Các bước thực hiện của Tìm kiếm nhị phân:

Khởi tạo hai con trỏ (hoặc chỉ số): Một con trỏ low trỏ đến phần tử đầu tiên của mảng (hoặc phạm vi tìm kiếm hiện tại) và một con trỏ high trỏ đến phần tử cuối cùng.
Lặp lại quá trình: Trong khi low vẫn nhỏ hơn hoặc bằng high:
- Tính toán vị trí trung tâm (mid) của phạm vi tìm kiếm hiện tại: mid = (low + high) / 2. Lưu ý nhỏ: Để tránh tràn số với các mảng cực lớn, công thức an toàn hơn thường dùng là mid = low + (high - low) / 2.
- So sánh arr[mid] với target:
  - Nếu arr[mid] bằng target: Tuyệt vời! Chúng ta đã tìm thấy phần tử tại vị trí mid. Kết thúc tìm kiếm và trả về mid.
  - Nếu arr[mid] nhỏ hơn target: Điều này có nghĩa là target (nếu có) phải nằm ở nửa bên phải của mid (vì mảng đã sắp xếp tăng dần). Chúng ta loại bỏ nửa bên trái và cập nhật phạm vi tìm kiếm bằng cách đặt low = mid + 1.
  - Nếu arr[mid] lớn hơn target: Tương tự, target (nếu có) phải nằm ở nửa bên trái của mid. Chúng ta loại bỏ nửa bên phải và cập nhật phạm vi tìm kiếm bằng cách đặt high = mid - 1.
Kết thúc tìm kiếm: Nếu vòng lặp kết thúc (khi low > high), điều đó có nghĩa là phạm vi tìm kiếm đã bị thu hẹp lại cho đến khi không còn phần tử nào (low vượt quá high), và chúng ta không tìm thấy target trong mảng. Trả về một giá trị đặc biệt để chỉ báo không tìm thấy (thường là -1).

Mỗi lần lặp, chúng ta đã loại bỏ được một nửa số phần tử còn lại trong phạm vi tìm kiếm. Đây chính là lý do tạo nên hiệu quả vượt trội của thuật toán này!

Độ phức tạp thời gian: Sự khác biệt lớn!

Vì mỗi bước lặp lại chia đôi phạm vi tìm kiếm, số bước tối đa cần thiết để tìm kiếm trong một mảng có n phần tử là số lần bạn có thể chia n cho 2 cho đến khi chỉ còn 1 phần tử. Con số này chính là log₂n.

Độ phức tạp thời gian của Tìm kiếm nhị phân là O(log n).

Hãy so sánh O(n) của Tìm kiếm tuyến tính với O(log n) của Tìm kiếm nhị phân:

Mảng có 100 phần tử: Tuyến tính \(100 bước, Nhị phân \)log₂(100) ≈ 7 bước.
Mảng có 1.000.000 phần tử: Tuyến tính \(1.000.000 bước, Nhị phân \)log₂(1.000.000) ≈ 20 bước.
Mảng có 1.000.000.000 phần tử: Tuyến tính \(1.000.000.000 bước, Nhị phân \)log₂(1.000.000.000) ≈ 30 bước.

Bạn thấy sự khác biệt chưa? Với dữ liệu lớn, O(log n) nhanh hơn O(n) một cách ngoạn mục!

Cài đặt Tìm kiếm nhị phân bằng C++

Có hai cách cài đặt phổ biến cho Tìm kiếm nhị phân: lặp (iterative) và đệ quy (recursive). Cả hai đều có cùng độ phức tạp thời gian O(log n), nhưng cách lặp thường được ưa chuộng hơn trong thực tế vì không tốn chi phí quản lý stack cho các hàm đệ quy (và tránh nguy cơ tràn stack với mảng cực lớn, dù hiếm gặp).

Cài đặt dạng lặp (Iterative Binary Search)

Đây là cách cài đặt trực tiếp và thường được khuyên dùng:

#include <iostream>
#include <vector>
#include <algorithm> // Cần để sử dụng std::sort nếu mảng chưa sắp xếp

// Hàm thực hiện Tìm kiếm nhị phân dạng lặp
// Trả về chỉ số của target nếu tìm thấy, ngược lại trả về -1
int binarySearchIterative(const std::vector<int>& arr, int target) {
    int low = 0; // Chỉ số bắt đầu phạm vi tìm kiếm
    int high = arr.size() - 1; // Chỉ số kết thúc phạm vi tìm kiếm

    // Lặp lại quá trình chia đôi cho đến khi phạm vi tìm kiếm hợp lệ (low <= high)
    while (low <= high) {
        // Tính chỉ số điểm giữa
        // Công thức an toàn hơn: low + (high - low) / 2
        // (low + high) / 2 có thể gây tràn số nếu low và high rất lớn
        int mid = low + (high - low) / 2;

        // Kiểm tra nếu target bằng phần tử tại điểm giữa
        if (arr[mid] == target) {
            return mid; // Tìm thấy! Trả về chỉ số
        }
        // Nếu target lớn hơn phần tử tại điểm giữa,
        // nghĩa là target nằm ở nửa bên phải
        else if (arr[mid] < target) {
            low = mid + 1; // Bỏ qua mid và nửa trái, cập nhật low
        }
        // Nếu target nhỏ hơn phần tử tại điểm giữa,
        // nghĩa là target nằm ở nửa bên trái
        else { // arr[mid] > target
            high = mid - 1; // Bỏ qua mid và nửa phải, cập nhật high
        }
    }

    // Nếu vòng lặp kết thúc mà không tìm thấy, trả về -1
    return -1;
}

int main() {
    // Dữ liệu BẮT BUỘC phải được sắp xếp
    std::vector<int> sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

    int target1 = 23;
    int target2 = 50;
    int target3 = 2;
    int target4 = 91;

    // Tìm kiếm target1
    int index1 = binarySearchIterative(sortedArray, target1);
    if (index1 != -1) {
        std::cout << "Target " << target1 << " found at index " << index1 << std::endl; // Output: Target 23 found at index 5
    } else {
        std::cout << "Target " << target1 << " not found in the array." << std::endl;
    }

    // Tìm kiếm target2
    int index2 = binarySearchIterative(sortedArray, target2);
    if (index2 != -1) {
        std::cout << "Target " << target2 << " found at index " << index2 << std::endl;
    } else {
        std::cout << "Target " << target2 << " not found in the array." << std::endl; // Output: Target 50 not found in the array.
    }

    // Tìm kiếm target3 (phần tử đầu)
    int index3 = binarySearchIterative(sortedArray, target3);
    if (index3 != -1) {
        std::cout << "Target " << target3 << " found at index " << index3 << std::endl; // Output: Target 2 found at index 0
    } else {
        std::cout << "Target " << target3 << " not found in the array." << std::endl;
    }

    // Tìm kiếm target4 (phần tử cuối)
    int index4 = binarySearchIterative(sortedArray, target4);
    if (index4 != -1) {
        std::cout << "Target " << target4 << " found at index " << index4 << std::endl; // Output: Target 91 found at index 9
    } else {
        std::cout << "Target " << target4 << " not found in the array." << std::endl;
    }

    return 0;
}

Giải thích code lặp:

Hàm binarySearchIterative nhận vào một vector arr (đã sắp xếp) và giá trị target cần tìm. Sử dụng const& để tránh sao chép vector và đảm bảo không thay đổi dữ liệu gốc.
low và high là hai biến kiểu int đánh dấu phạm vi tìm kiếm hiện tại. Ban đầu, chúng bao trùm toàn bộ mảng.
Vòng lặp while (low <= high) tiếp tục chừng nào phạm vi tìm kiếm còn có ít nhất một phần tử. Nếu low vượt quá high, phạm vi rỗng, tức là không tìm thấy.
mid = low + (high - low) / 2; tính chỉ số chính giữa. Công thức này an toàn hơn (low + high) / 2 khi low và high rất lớn gần giới hạn kiểu dữ liệu, tránh tràn số.
Ba nhánh if-else if-else kiểm tra giá trị tại arr[mid] so với target:
- Nếu bằng: Tìm thấy, trả về mid.
- Nếu nhỏ hơn: target phải ở bên phải mid. Cập nhật low = mid + 1 để bắt đầu tìm kiếm từ phần tử sau mid.
- Nếu lớn hơn: target phải ở bên trái mid. Cập nhật high = mid - 1 để kết thúc tìm kiếm ở phần tử trước mid.
Nếu vòng lặp kết thúc mà lệnh return mid; chưa được gọi, nghĩa là không tìm thấy target, hàm sẽ trả về -1.
Hàm main minh họa cách sử dụng với một mảng đã sắp xếp và in kết quả tìm kiếm cho một vài giá trị khác nhau.

Cài đặt dạng đệ quy (Recursive Binary Search)

Cách đệ quy thể hiện rõ hơn ý tưởng chia để trị, nhưng cần cẩn thận với điều kiện dừng.

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm thực hiện Tìm kiếm nhị phân dạng đệ quy
// Trả về chỉ số của target nếu tìm thấy, ngược lại trả về -1
// Hàm trợ giúp này tìm kiếm trong phạm vi [low, high]
int binarySearchRecursiveHelper(const std::vector<int>& arr, int target, int low, int high) {
    // Điều kiện dừng: Phạm vi tìm kiếm không hợp lệ (không tìm thấy)
    if (low > high) {
        return -1;
    }

    // Tính chỉ số điểm giữa
    int mid = low + (high - low) / 2;

    // Trường hợp cơ bản: Tìm thấy target
    if (arr[mid] == target) {
        return mid;
    }
    // Nếu target lớn hơn phần tử tại điểm giữa,
    // gọi đệ quy tìm kiếm ở nửa bên phải
    else if (arr[mid] < target) {
        return binarySearchRecursiveHelper(arr, target, mid + 1, high);
    }
    // Nếu target nhỏ hơn phần tử tại điểm giữa,
    // gọi đệ quy tìm kiếm ở nửa bên trái
    else { // arr[mid] > target
        return binarySearchRecursiveHelper(arr, target, low, mid - 1);
    }
}

// Hàm wrapper cho Tìm kiếm nhị phân đệ quy
int binarySearchRecursive(const std::vector<int>& arr, int target) {
    return binarySearchRecursiveHelper(arr, target, 0, arr.size() - 1);
}

int main() {
    // Dữ liệu BẮT BU buộc phải được sắp xếp
    std::vector<int> sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

    int target1 = 16;
    int target2 = 99;
    int target3 = 5;
    int target4 = 72;

    // Tìm kiếm target1
    int index1 = binarySearchRecursive(sortedArray, target1);
    if (index1 != -1) {
        std::cout << "Target " << target1 << " found at index " << index1 << std::endl; // Output: Target 16 found at index 4
    } else {
        std::cout << "Target " << target1 << " not found in the array." << std::endl;
    }

    // Tìm kiếm target2
    int index2 = binarySearchRecursive(sortedArray, target2);
    if (index2 != -1) {
        std::cout << "Target " << target2 << " found at index " << index2 << std::endl;
    } else {
        std::cout << "Target " << target2 << " not found in the array." << std::endl; // Output: Target 99 not found in the array.
    }

    // Tìm kiếm target3 (phần tử đầu)
    int index3 = binarySearchRecursive(sortedArray, target3);
    if (index3 != -1) {
        std::cout << "Target " << target3 << " found at index " << index3 << std::endl; // Output: Target 5 found at index 1
    } else {
        std::cout << "Target " << target3 << " not found in the array." << std::endl;
    }

    // Tìm kiếm target4 (phần tử cuối)
    int index4 = binarySearchRecursive(sortedArray, target4);
    if (index4 != -1) {
        std::cout << "Target " << target4 << " found at index " << index4 << std::endl; // Output: Target 72 found at index 8
    } else {
        std::cout << "Target " << target4 << " not found in the array." << std::endl;
    }

    return 0;
}

Giải thích code đệ quy:

Hàm chính binarySearchRecursive chỉ là một "hàm bao" (wrapper function) gọi hàm đệ quy thực tế binarySearchRecursiveHelper với phạm vi ban đầu là toàn bộ mảng (0 đến arr.size() - 1).
Hàm binarySearchRecursiveHelper nhận thêm hai tham số low và high để xác định phạm vi tìm kiếm trong lần gọi hiện tại.
Điều kiện dừng (Base Case): if (low > high) là điều kiện dừng quan trọng nhất của đệ quy. Khi phạm vi low vượt quá high, điều này có nghĩa là chúng ta đã thu hẹp không gian tìm kiếm đến mức không còn phần tử nào và target không được tìm thấy. Hàm trả về -1.
Tính mid tương tự như bản lặp.
Nếu arr[mid] == target: Đây là trường hợp cơ bản thứ hai, tìm thấy phần tử. Trả về mid.
Nếu arr[mid] < target: target nằm bên phải. Hàm gọi đệ quy chính nó nhưng chỉ trên phạm vi từ mid + 1 đến high. Kết quả của lời gọi đệ quy này sẽ là kết quả cuối cùng.
Nếu arr[mid] > target: target nằm bên trái. Hàm gọi đệ quy chính nó nhưng chỉ trên phạm vi từ low đến mid - 1. Kết quả của lời gọi đệ quy này cũng là kết quả cuối cùng.
Cả hai bản lặp và đệ quy đều thực hiện cùng một logic chia đôi và loại bỏ, dẫn đến cùng độ phức tạp O(log n).

Ứng dụng của Tìm kiếm nhị phân

Tìm kiếm nhị phân không chỉ giới hạn ở việc tìm kiếm đơn giản trong mảng. Ý tưởng cốt lõi của nó - chia đôi không gian tìm kiếm dựa trên một điều kiện đơn điệu (monotonic condition) - được ứng dụng rộng rãi trong nhiều bài toán khác:

Tìm kiếm trên mảng đã sắp xếp: Đây là ứng dụng cơ bản nhất mà chúng ta vừa tìm hiểu. Tìm một giá trị, kiểm tra sự tồn tại, tìm vị trí đầu tiên/cuối cùng của một phần tử khi có trùng lặp.
Tìm kiếm trong các cấu trúc dữ liệu sắp xếp: Cây tìm kiếm nhị phân (Binary Search Tree - BST) về cơ bản hoạt động dựa trên nguyên tắc của Tìm kiếm nhị phân để tìm kiếm, thêm, xóa các phần tử.
Tìm căn bậc hai: Để tìm căn bậc hai của một số X, bạn có thể tìm kiếm nhị phân trong khoảng từ 0 đến X (hoặc từ 0 đến 1 nếu X < 1). Với một giá trị mid trong khoảng, bạn kiểm tra xem mid * mid có bằng X, lớn hơn X hay nhỏ hơn X để thu hẹp phạm vi tìm kiếm.
Tìm kiếm "trên kết quả" (Binary Search on the Answer): Đây là một kỹ thuật mạnh mẽ trong lập trình thi đấu. Khi bạn cần tìm một giá trị X sao cho một điều kiện nào đó được thỏa mãn, và điều kiện này có tính chất đơn điệu (ví dụ: nếu điều kiện đúng với X, thì nó cũng đúng với mọi giá trị nhỏ hơn X, hoặc mọi giá trị lớn hơn X), bạn có thể sử dụng tìm kiếm nhị phân trên khoảng giá trị có thể có của X. Ví dụ: tìm kích thước lớn nhất của một nhóm các đối tượng có thể được vận chuyển trên xe tải có trọng tải tối đa cho phép (điều kiện: nếu tôi có thể vận chuyển nhóm đối tượng với kích thước X, tôi cũng có thể vận chuyển nhóm đối tượng có kích thước nhỏ hơn X).
Tìm kiếm trong từ điển hoặc cơ sở dữ liệu có chỉ mục: Các hệ thống quản lý dữ liệu thường sử dụng các cấu trúc dựa trên nguyên tắc tìm kiếm nhị phân (như B-tree) để thực hiện các truy vấn tìm kiếm một cách nhanh chóng.
Các bài toán tìm kiếm biến thể: Tìm kiếm giá trị nhỏ nhất/lớn nhất thỏa mãn một điều kiện, tìm phần tử xuất hiện đầu tiên/cuối cùng trong mảng có trùng lặp, tìm floor (phần tử lớn nhất <= target), tìm ceiling (phần tử nhỏ nhất >= target),... đều có thể được giải quyết bằng cách điều chỉnh logic của Tìm kiếm nhị phân cơ bản.

Lưu ý quan trọng

Dữ liệu phải được sắp xếp: Đây là yêu cầu bắt buộc. Nếu dữ liệu chưa sắp xếp, bạn phải thực hiện bước sắp xếp trước khi áp dụng Tìm kiếm nhị phân. Chi phí sắp xếp cần được tính vào tổng chi phí nếu đó là một phần của bài toán.
Truy cập ngẫu nhiên (Random Access): Tìm kiếm nhị phân hiệu quả nhất trên các cấu trúc dữ liệu cho phép truy cập ngẫu nhiên O(1) đến bất kỳ phần tử nào bằng chỉ số, như mảng (array) hoặc vector trong C++. Trên các cấu trúc truy cập tuần tự (sequential access) như danh sách liên kết (linked list), việc tính mid và truy cập arr[mid] sẽ tốn O(n) thời gian cho mỗi bước, làm mất đi lợi thế O(log n) của thuật toán.

Bài tập ví dụ:

Tìm cặp số

Trong một buổi học, giáo sư đã đưa ra một bài toán thú vị cho FullHouse Dev. Bài toán yêu cầu tìm số cặp số thỏa mãn một điều kiện đặc biệt trong một mảng. Với tinh thần ham học hỏi, FullHouse Dev đã bắt tay vào giải quyết thử thách này.

Bài toán

Cho một mảng \(A\) có độ dài \(n\). Nhiệm vụ là tìm số lượng cặp số có thứ tự \((i, j)\) thỏa mãn điều kiện: \(A[i]\) phải chia hết cho \(A[j]\).

INPUT FORMAT:

Dòng đầu tiên chứa một số nguyên \(n\).
Dòng thứ hai chứa \(n\) số nguyên cách nhau bởi dấu cách, biểu thị các phần tử của mảng \(A\).

OUTPUT FORMAT:

In ra số lượng cặp số có thứ tự \((i, j)\) thỏa mãn điều kiện trên.

Ràng buộc:

\(1 \leq n \leq 10^5\)

Ví dụ

INPUT

3
1 2 3

OUTPUT

Giải thích

Với mọi cặp số \((i, j)\) trong mảng này, điều kiện chia hết đều được thỏa mãn. Do đó, đáp án là 6. Okay, đây là hướng dẫn giải bài "Tìm cặp số" một cách hiệu quả:

Phân tích bài toán: Cần tìm số cặp có thứ tự (i, j) sao cho A[i] chia hết cho A[j].
Brute Force (Duyệt trâu): Cách đơn giản nhất là duyệt mọi cặp (i, j) với 0 <= i < n và 0 <= j < n, sau đó kiểm tra điều kiện A[i] % A[j] == 0. Nếu đúng thì tăng biến đếm.
Nhược điểm Brute Force: Độ phức tạp là O(n^2). Với n lên đến 10^5, O(n^2) là quá chậm (khoảng 10^10 phép tính), sẽ vượt quá thời gian cho phép.
Tìm cách tối ưu: Điều kiện A[i] % A[j] == 0 có nghĩa là A[i] là bội của A[j]. Thay vì duyệt từng cặp chỉ mục (i, j), ta có thể nghĩ cách khác dựa trên giá trị của các phần tử.
Ý tưởng tối ưu: Ta có thể đếm số lần xuất hiện của mỗi giá trị trong mảng A. Sau đó, với mỗi giá trị v xuất hiện trong mảng (giá trị này có thể đóng vai trò là A[j]), ta tìm tất cả các bội m của v mà cũng xuất hiện trong mảng (các bội này có thể đóng vai trò là A[i]).
Các bước giải chi tiết:
- Đọc vào n và các phần tử của mảng A.
- Sử dụng một cấu trúc dữ liệu (ví dụ: mảng tần suất hoặc map) để đếm số lần xuất hiện của mỗi giá trị khác nhau trong mảng A. Đồng thời, tìm giá trị lớn nhất max_val trong mảng A.
- Khởi tạo một biến đếm tổng số cặp (sử dụng kiểu dữ liệu long long để tránh tràn số, vì số cặp có thể rất lớn).
- Duyệt qua tất cả các giá trị v từ 1 đến max_val.
- Đối với mỗi giá trị v, nếu v có xuất hiện trong mảng (tần suất > 0), thì v có thể là giá trị của A[j].
- Nếu v có xuất hiện, ta tiếp tục duyệt qua các bội của v: m = v, 2v, 3v, ... cho đến khi m > max_val.
- Đối với mỗi bội m, nếu m cũng có xuất hiện trong mảng (tần suất > 0), thì m có thể là giá trị của A[i].
- Số cặp (i, j) mà A[j] = v và A[i] = m sẽ bằng (số lần xuất hiện của v) * (số lần xuất hiện của m). Cộng giá trị này vào biến đếm tổng.
- Sau khi duyệt xong tất cả các giá trị v và các bội m của chúng, biến đếm tổng sẽ là đáp án cần tìm.
Độ phức tạp của thuật toán tối ưu:
- Đếm tần suất và tìm max_val: O(n) hoặc O(n log n) nếu dùng map.
- Vòng lặp chính: Duyệt v từ 1 đến max_val. Vòng lặp trong duyệt các bội m của v. Tổng số lần lặp của vòng lặp trong cho tất cả các giá trị v là khoảng max_val * (1/1 + 1/2 + ... + 1/max_val), tương đương O(max_val * log(max_val)).
- Tổng độ phức tạp: O(n + max_val * log(max_val)). Nếu max_val không quá lớn (ví dụ, cỡ 10^6 như các bài competitive programming thường gặp), đây là một giải pháp hiệu quả, nhanh hơn nhiều so với O(n^2).

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.