Bài 23.1: Bài tập thực hành binary_search trong C++

Chào mừng các bạn quay trở lại với series blog về C++! Hôm nay, chúng ta sẽ cùng nhau khám phá một trong những thuật toán tìm kiếm kinh điển và cực kỳ hiệu quả: Tìm kiếm nhị phân (Binary Search). Nếu bạn đã từng làm việc với dữ liệu lớn hoặc cần tìm kiếm thông tin một cách nhanh chóng, binary search chính là người bạn đồng hành đáng tin cậy.

Trong bài viết này, chúng ta sẽ đi sâu vào:

Binary Search là gì và nó hoạt động như thế nào.
Điều kiện tiên quyết để sử dụng Binary Search.
Cách tự triển khai Binary Search bằng C++.
Cách sử dụng các hàm Binary Search có sẵn trong Thư viện chuẩn C++ (binary_search, lower_bound, upper_bound).
Tại sao Binary Search lại hiệu quả đến vậy.

Hãy bắt đầu hành trình khám phá sức mạnh của Binary Search trong C++!

Binary Search là gì?

Binary Search (hay tìm kiếm nhị phân) là một thuật toán tìm kiếm hiệu quả dùng để tìm kiếm vị trí của một phần tử trong một mảng hoặc danh sách đã được sắp xếp. Nó hoạt động dựa trên nguyên tắc "chia để trị" (divide and conquer): thay vì duyệt qua từng phần tử một cách tuần tự (như tìm kiếm tuyến tính - linear search), binary search liên tục chia đôi phạm vi tìm kiếm, loại bỏ một nửa các phần tử không chứa giá trị cần tìm.

Hãy tưởng tượng bạn đang tìm một từ trong cuốn từ điển dày cộp. Bạn sẽ không bắt đầu từ trang đầu tiên và đọc từng từ một đúng không? Thay vào đó, bạn mở sách ở khoảng giữa, xem từ đó nằm trước hay sau trang bạn đang xem, rồi lại tiếp tục mở ở giữa nửa phía trước hoặc nửa phía sau. Cứ như vậy, bạn nhanh chóng thu hẹp phạm vi và tìm thấy từ cần tìm. Binary Search hoạt động theo cách tương tự!

Điều kiện Tiên Quyết: Dữ liệu Phải Được Sắp Xếp!

Đây là điều quan trọng nhất cần nhớ về Binary Search. Thuật toán này chỉ hoạt động trên dữ liệu đã được sắp xếp (theo thứ tự tăng dần hoặc giảm dần). Nếu dữ liệu chưa được sắp xếp, bạn cần phải sắp xếp nó trước khi áp dụng Binary Search. Nếu không, kết quả tìm kiếm sẽ hoàn toàn không chính xác.

Cách Hoạt Động Của Binary Search

Các bước cơ bản của thuật toán Binary Search trên một mảng đã sắp xếp tăng dần để tìm giá trị target:

Xác định phạm vi tìm kiếm ban đầu: từ phần tử đầu tiên (chỉ số low = 0) đến phần tử cuối cùng (chỉ số high = kích thước_mảng - 1).

Lặp lại chừng nào low <= high: a. Tính chỉ số của phần tử ở giữa phạm vi hiện tại: mid = low + (high - low) / 2. (Cách tính này giúp tránh tràn số khi low và high rất lớn so với cách tính đơn giản (low + high) / 2). b. So sánh phần tử ở vị trí mid với giá trị target:

*   Nếu `mảng[mid] == target`: Tìm thấy! Trả về chỉ số `mid`.
*   Nếu `mảng[mid] < target`: Giá trị cần tìm *lớn hơn* phần tử ở giữa. Điều này có nghĩa là `target` (nếu có) phải nằm ở nửa bên phải của phạm vi tìm kiếm hiện tại. Cập nhật phạm vi tìm kiếm: `low = mid + 1`.
*   Nếu `mảng[mid] > target`: Giá trị cần tìm *nhỏ hơn* phần tử ở giữa. Điều này có nghĩa là `target` (nếu có) phải nằm ở nửa bên trái của phạm vi tìm kiếm hiện tại. Cập nhật phạm vi tìm kiếm: `high = mid - 1`.

Nếu vòng lặp kết thúc mà không tìm thấy phần tử (tức là low > high), điều đó có nghĩa là target không có trong mảng. Trả về một giá trị đặc biệt (thường là -1) để báo hiệu không tìm thấy.

Tự Triển Khai Binary Search Bằng C++

Việc tự triển khai giúp bạn hiểu rõ hơn về cơ chế hoạt động của thuật toán. Dưới đây là một ví dụ về hàm Binary Search cơ bản trong C++:

#include <iostream>
#include <vector>

using namespace std;

int timNhiPhan(const vector<int>& v, int x) {
    int l = 0;
    int h = v.size() - 1;

    while (l <= h) {
        int giua = l + (h - l) / 2;
        if (v[giua] == x) {
            return giua;
        } else if (v[giua] < x) {
            l = giua + 1;
        } else {
            h = giua - 1;
        }
    }
    return -1;
}

int main() {
    vector<int> duLieu = {1, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int x1 = 23;
    int x2 = 40;

    int chiSo1 = timNhiPhan(duLieu, x1);
    if (chiSo1 != -1) {
        cout << "Tim thay " << x1 << " tai chi so: " << chiSo1 << endl;
    } else {
        cout << x1 << " khong co trong mang." << endl;
    }

    int chiSo2 = timNhiPhan(duLieu, x2);
    if (chiSo2 != -1) {
        cout << "Tim thay " << x2 << " tai chi so: " << chiSo2 << endl;
    } else {
        cout << x2 << " khong co trong mang." << endl;
    }

    return 0;
}

Kết quả chạy code trên:

Tim thay 23 tai chi so: 5
40 khong co trong mang.

Ví dụ này cho thấy cách triển khai Binary Search từ đầu, giúp bạn nắm vững logic cốt lõi. Tuy nhiên, trong thực tế, việc sử dụng các hàm có sẵn trong Thư viện chuẩn C++ thường là lựa chọn tốt hơn vì chúng đã được kiểm thử kỹ lưỡng và tối ưu hóa.

Sử Dụng Các Hàm Binary Search Trong Thư Viện Chuẩn C++

Thư viện chuẩn C++ (<algorithm>) cung cấp các hàm mạnh mẽ dựa trên Binary Search mà bạn nên tận dụng.

1. `binary_search`

Hàm này đơn giản nhất, nó chỉ kiểm tra xem một giá trị có tồn tại trong phạm vi đã cho hay không. Nó trả về true nếu tìm thấy, false nếu không.

Yêu cầu: Phạm vi dữ liệu phải được sắp xếp.
Prototype: bool binary_search(ForwardIterator first, ForwardIterator last, const T& val);

Ví dụ:

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

using namespace std;

int main() {
    vector<int> duLieu = {1, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int x1 = 16;
    int x2 = 50;

    if (binary_search(duLieu.begin(), duLieu.end(), x1)) {
        cout << x1 << " co ton tai trong vector." << endl;
    } else {
        cout << x1 << " khong ton tai trong vector." << endl;
    }

    if (binary_search(duLieu.begin(), duLieu.end(), x2)) {
        cout << x2 << " co ton tai trong vector." << endl;
    } else {
        cout << x2 << " khong ton tai trong vector." << endl;
    }

    return 0;
}

Kết quả chạy code trên:

16 co ton tai trong vector.
50 khong ton tai trong vector.

2. `lower_bound` và `upper_bound`

Hai hàm này mạnh mẽ hơn, chúng không chỉ tìm kiếm mà còn trả về iterator đến vị trí quan trọng trong mảng đã sắp xếp. Chúng hữu ích khi bạn cần biết vị trí để chèn phần tử mới mà vẫn giữ được thứ tự, hoặc khi bạn cần tìm tất cả các lần xuất hiện của một giá trị (nếu có nhiều phần tử trùng lặp).

Yêu cầu: Phạm vi dữ liệu phải được sắp xếp.
lower_bound: Trả về một iterator trỏ đến phần tử đầu tiên trong phạm vi không nhỏ hơn (>=) giá trị đã cho. Nếu không có phần tử nào như vậy, nó trả về iterator đến last.
upper_bound: Trả về một iterator trỏ đến phần tử đầu tiên trong phạm vi lớn hơn (>) giá trị đã cho. Nếu không có phần tử nào như vậy, nó trả về iterator đến last.

Ví dụ sử dụng lower_bound để tìm vị trí và kiểm tra sự tồn tại:

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

using namespace std;

int main() {
    vector<int> duLieu = {1, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int x1 = 23;
    int x2 = 40;

    auto it1 = lower_bound(duLieu.begin(), duLieu.end(), x1);

    if (it1 != duLieu.end() && *it1 == x1) {
        int chiSo1 = distance(duLieu.begin(), it1);
        cout << "Tim thay " << x1 << " tai chi so (qua lower_bound): " << chiSo1 << endl;
    } else {
        int viTriChen1 = distance(duLieu.begin(), it1);
        cout << x1 << " khong co trong vector. Vi tri co the chen la: " << viTriChen1 << endl;
    }

    cout << "---" << endl;

    auto it2 = lower_bound(duLieu.begin(), duLieu.end(), x2);
    if (it2 != duLieu.end() && *it2 == x2) {
        int chiSo2 = distance(duLieu.begin(), it2);
        cout << "Tim thay " << x2 << " tai chi so (qua lower_bound): " << chiSo2 << endl;
    } else {
        int viTriChen2 = distance(duLieu.begin(), it2);
        cout << x2 << " khong co trong vector. Vi tri co the chen la: " << viTriChen2 << endl;
    }

    cout << "---" << endl;

    vector<int> duLieuTrung = {1, 5, 5, 5, 8, 12, 16, 23};
    int xTrung = 5;

    auto dau = lower_bound(duLieuTrung.begin(), duLieuTrung.end(), xTrung);
    auto cuoi = upper_bound(duLieuTrung.begin(), duLieuTrung.end(), xTrung);

    if (dau != duLieuTrung.end() && *dau == xTrung) {
        int posDau = distance(duLieuTrung.begin(), dau);
        int posCuoi = distance(duLieuTrung.begin(), cuoi) - 1;

        cout << "So " << xTrung << " tim thay lan dau tien tai chi so: " << posDau << endl;
        cout << "So " << xTrung << " xuat hien trong pham vi chi so tu " << posDau << " den " << posCuoi << endl;
        cout << "So luong " << xTrung << " la: " << distance(dau, cuoi) << endl;
    } else {
        cout << xTrung << " khong co trong vector." << endl;
    }

    return 0;
}

Kết quả chạy code trên:

Tim thay 23 tai chi so (qua lower_bound): 5
---
40 khong co trong vector. Vi tri co the chen la: 8
---
So 5 tim thay lan dau tien tai chi so: 1
So 5 xuat hien trong pham vi chi so tu 1 den 3
So luong 5 la: 3

Các hàm lower_bound và upper_bound cực kỳ linh hoạt và là công cụ không thể thiếu khi làm việc với các tập dữ liệu đã sắp xếp trong C++.

Tại Sao Binary Search Lại Hiệu Quả?

Sức mạnh của Binary Search nằm ở tốc độ của nó. Với mỗi bước so sánh, nó loại bỏ được một nửa số phần tử còn lại. Điều này dẫn đến độ phức tạp thời gian là O(log n), trong đó 'n' là số lượng phần tử.

Để dễ hình dung, hãy so sánh với tìm kiếm tuyến tính (duyệt từng phần tử - O(n)):

Tìm kiếm tuyến tính trong 1000 phần tử có thể mất tối đa 1000 bước.
Binary Search trong 1000 phần tử chỉ mất khoảng log2(1000) ≈ 10 bước!
Tìm kiếm tuyến tính trong 1 triệu phần tử có thể mất tối đa 1 triệu bước.
Binary Search trong 1 triệu phần tử chỉ mất khoảng log2(1,000,000) ≈ 20 bước!

Sự khác biệt này trở nên đồ sộ khi làm việc với tập dữ liệu lớn. Mặc dù Binary Search đòi hỏi dữ liệu phải được sắp xếp (việc sắp xếp có thể tốn thời gian, ví dụ O(n log n) với các thuật toán hiệu quả như Merge Sort hay Quick Sort), nhưng nếu bạn thực hiện nhiều thao tác tìm kiếm trên cùng một tập dữ liệu, chi phí sắp xếp ban đầu sẽ được bù đắp nhanh chóng bởi tốc độ tìm kiếm sau đó.

Comments

There are no comments at the moment.