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> // Sử dụng vector để thuận tiện, có thể thay bằng mảng tĩnh

// Hàm Binary Search cho vector đã sắp xếp tăng dần
// Trả về chỉ số của phần tử nếu tìm thấy, ngược lại trả về -1
int binarySearchManual(const vector<int>& arr, int target) {
    int low = 0; // Chỉ số bắt đầu của phạm vi tìm kiếm
    int high = arr.size() - 1; // Chỉ số kết thúc của phạm vi tìm kiếm

    // Lặp khi phạm vi tìm kiếm còn hợp lệ
    while (low <= high) {
        // Tính chỉ số phần tử ở giữa
        // Sử dụng cách này để tránh tràn số khi low và high lớn
        int mid = low + (high - low) / 2;

        // So sánh phần tử ở giữa với giá trị cần tìm
        if (arr[mid] == target) {
            return mid; // Tìm thấy, trả về chỉ số
        } else if (arr[mid] < target) {
            // target lớn hơn phần tử giữa, tìm kiếm ở nửa bên phải
            low = mid + 1;
        } else { // arr[mid] > target
            // target nhỏ hơn phần tử giữa, tìm kiếm ở nửa bên trái
            high = mid - 1;
        }
    }

    // Không tìm thấy phần tử sau khi vòng lặp kết thúc
    return -1;
}

int main() {
    // Dữ liệu PHẢI được sắp xếp
    vector<int> data = {1, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target1 = 23; // Giá trị cần tìm (có trong mảng)
    int target2 = 40; // Giá trị cần tìm (không có trong mảng)

    // Tìm kiếm target1
    int index1 = binarySearchManual(data, target1);
    if (index1 != -1) {
        cout << "Tim thay " << target1 << " tai chi so: " << index1 << endl;
    } else {
        cout << target1 << " khong co trong mang." << endl;
    }

    // Tìm kiếm target2
    int index2 = binarySearchManual(data, target2);
    if (index2 != -1) {
        cout << "Tim thay " << target2 << " tai chi so: " << index2 << endl;
    } else {
        cout << target2 << " khong co trong mang." << endl;
    }

    return 0;
}

Giải thích Code:

Hàm binarySearchManual nhận vào một vector<int> (đã sắp xếp) và giá trị target cần tìm.
low và high định nghĩa phạm vi tìm kiếm hiện tại bằng các chỉ số.
Vòng lặp while (low <= high) tiếp tục chừng nào phạm vi tìm kiếm còn hợp lệ (chỉ số bắt đầu không vượt quá chỉ số kết thúc).
mid là chỉ số của phần tử ở giữa. Công thức low + (high - low) / 2 đảm bảo mid nằm trong phạm vi và an toàn hơn khi low và high rất lớn.
So sánh arr[mid] với target và điều chỉnh low hoặc high để thu hẹp phạm vi tìm kiếm.
Nếu target được tìm thấy, hàm trả về chỉ số mid.
Nếu vòng lặp kết thúc mà không tìm thấy, hàm trả về -1.
Trong main, chúng ta khởi tạo một vector đã sắp xếp và gọi hàm binarySearchManual với hai giá trị target khác nhau để minh họa.

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> // Cần include <algorithm> cho binary_search

int main() {
    // Dữ liệu PHẢI được sắp xếp
    vector<int> data = {1, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target1 = 16; // Có trong vector
    int target2 = 50; // Không có trong vector

    // Kiểm tra sự tồn tại của target1
    if (binary_search(data.begin(), data.end(), target1)) {
        cout << target1 << " co ton tai trong vector." << endl;
    } else {
        cout << target1 << " khong ton tai trong vector." << endl;
    }

    // Kiểm tra sự tồn tại của target2
    if (binary_search(data.begin(), data.end(), target2)) {
        cout << target2 << " co ton tai trong vector." << endl;
    } else {
        cout << target2 << " khong ton tai trong vector." << endl;
    }

    return 0;
}

Giải thích Code:

Chúng ta sử dụng vector và cung cấp các iterator đến điểm bắt đầu (data.begin()) và điểm kết thúc (data.end()) của phạm vi tìm kiếm.
binary_search thực hiện việc tìm kiếm và trả về bool.
Hàm này rất tiện lợi khi bạn chỉ cần biết liệu một phần tử có ở đó hay không, mà không cần biết vị trí chính xác của nó.

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> // Cần include <algorithm>
#include <iterator> // Cần include <iterator> để dùng distance

int main() {
    // Dữ liệu PHẢI được sắp xếp
    vector<int> data = {1, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target1 = 23; // Có trong vector
    int target2 = 40; // Không có trong vector
    int target3 = 5;  // Có trong vector

    // Sử dụng lower_bound để tìm vị trí tiềm năng cho target1 (23)
    auto it1 = lower_bound(data.begin(), data.end(), target1);

    // Kiểm tra xem có tìm thấy đúng giá trị target1 hay không
    // it1 != data.end() đảm bảo iterator hợp lệ (không trỏ ra ngoài cuối vector)
    // *it1 == target1 đảm bảo giá trị tại vị trí đó đúng là target1
    if (it1 != data.end() && *it1 == target1) {
        // Nếu tìm thấy, chúng ta có thể lấy chỉ số bằng distance
        int index1 = distance(data.begin(), it1);
        cout << "Tim thay " << target1 << " tai chi so (qua lower_bound): " << index1 << endl;
    } else {
        // Nếu không tìm thấy đúng giá trị, lower_bound trả về vị trí nên chèn
        int insert_pos1 = distance(data.begin(), it1);
        cout << target1 << " khong co trong vector. Vi tri co the chen la: " << insert_pos1 << endl;
    }

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

    // Sử dụng lower_bound cho target2 (40) - không có trong vector
    auto it2 = lower_bound(data.begin(), data.end(), target2);
    if (it2 != data.end() && *it2 == target2) {
         int index2 = distance(data.begin(), it2);
        cout << "Tim thay " << target2 << " tai chi so (qua lower_bound): " << index2 << endl;
    } else {
        int insert_pos2 = distance(data.begin(), it2);
        cout << target2 << " khong co trong vector. Vi tri co the chen la: " << insert_pos2 << endl;
    }

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

    // Sử dụng lower_bound và upper_bound để tìm phạm vi cho target3 (5) - giả sử có nhiều số 5
    // Để minh họa rõ hơn, ta tạo vector mới có số trùng lặp
    vector<int> data_duplicates = {1, 5, 5, 5, 8, 12, 16, 23};
    int target_dup = 5;

    auto lower = lower_bound(data_duplicates.begin(), data_duplicates.end(), target_dup);
    auto upper = upper_bound(data_duplicates.begin(), data_duplicates.end(), target_dup);

    // Kiểm tra xem target_dup có tồn tại không (lower_bound không trỏ tới end VÀ giá trị tại đó bằng target_dup)
     if (lower != data_duplicates.end() && *lower == target_dup) {
        int first_pos = distance(data_duplicates.begin(), lower);
        int last_pos = distance(data_duplicates.begin(), upper) - 1; // Vị trí cuối cùng của target_dup

        cout << "So " << target_dup << " tim thay lan dau tien tai chi so: " << first_pos << endl;
        cout << "So " << target_dup << " xuat hien trong pham vi chi so tu " << first_pos << " den " << last_pos << endl;
        cout << "So luong " << target_dup << " la: " << distance(lower, upper) << endl;

     } else {
         cout << target_dup << " khong co trong vector." << endl;
     }


    return 0;
}

Giải thích Code:

lower_bound(data.begin(), data.end(), target1) trả về iterator đến phần tử đầu tiên trong data không nhỏ hơn target1.
Nếu target1 có tồn tại trong vector, lower_bound sẽ trả về iterator trỏ đến lần xuất hiện đầu tiên của target1. Chúng ta kiểm tra điều này bằng cách đảm bảo iterator không phải data.end() và giá trị tại iterator đó (*it1) bằng target1.
Nếu target1 không tồn tại, lower_bound trả về iterator trỏ đến vị trí mà target1 nên được chèn vào để giữ cho vector được sắp xếp.
distance(data.begin(), it) được sử dụng để tính chỉ số (vị trí) của một iterator trong vector.
Ví dụ thứ ba minh họa cách dùng cả lower_bound và upper_bound để tìm phạm vi của các phần tử trùng lặp. lower trỏ đến lần xuất hiện đầu tiên của 5, còn upper trỏ đến phần tử đầu tiên lớn hơn 5 (tức là 8). Khoảng cách giữa lower và upper chính là số lần xuất hiện của 5.

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.