Bài 23.5: Bài tập thực hành kết hợp sắp xếp và tìm kiếm trong C++

Chào mừng bạn trở lại với chuỗi bài học về C++! Hôm nay, chúng ta sẽ không chỉ dừng lại ở việc tìm hiểu riêng rẽ các thuật toán sắp xếp hay tìm kiếm nữa, mà sẽ đi sâu vào một kỹ thuật cực kỳ mạnh mẽ và phổ biến trong lập trình thực tế: kết hợp sắp xếp và tìm kiếm.

Bạn đã bao giờ phải tìm kiếm một thông tin cụ thể trong một lượng dữ liệu khổng lồ chưa? Nếu dữ liệu đó không được sắp xếp theo một trật tự nào cả, công việc tìm kiếm có thể trở nên rất chậm chạp. Nhưng nếu dữ liệu đã được sắp xếp gọn gàng, việc tìm kiếm sẽ nhanh hơn gấp nhiều lần! Đó chính là sức mạnh mà chúng ta sẽ khám phá trong bài tập thực hành này.

Tại sao lại kết hợp Sắp xếp và Tìm kiếm?

Hãy tưởng tượng bạn có một danh bạ điện thoại gồm hàng ngàn số. Nếu danh bạ lộn xộn, bạn sẽ phải duyệt qua từng tên một từ đầu đến cuối cho đến khi tìm thấy người mình cần. Đây chính là tìm kiếm tuyến tính (linear search) - đơn giản nhưng kém hiệu quả khi dữ liệu lớn.

Nhưng nếu danh bạ được sắp xếp theo thứ tự bảng chữ cái? Bạn có thể mở danh bạ ở giữa, xem tên đó nằm ở nửa đầu hay nửa sau, rồi lại tiếp tục chia đôi phần còn lại để tìm kiếm. Quá trình này nhanh hơn rất nhiều so với duyệt từng mục. Đây là ý tưởng cốt lõi của tìm kiếm nhị phân (binary search) - một thuật toán cực kỳ hiệu quả nhưng chỉ hoạt động được trên dữ liệu đã được sắp xếp.

Vì vậy, chiến lược phổ biến là:

  1. Sắp xếp dữ liệu một lần ban đầu.
  2. Thực hiện tìm kiếm nhị phân (hoặc các thuật toán tìm kiếm hiệu quả khác dựa trên dữ liệu có thứ tự) nhiều lần trên dữ liệu đã được sắp xếp đó.

Chi phí để sắp xếp (thường là O(N log N)) có thể đáng kể, nhưng nếu bạn cần thực hiện nhiều thao tác tìm kiếm sau đó, lợi ích của việc tìm kiếm nhị phân tốc độ cao (O(log N)) sẽ nhanh chóng bù đắp chi phí sắp xếp ban đầu.

Ví dụ 1: Tìm kiếm trên mảng số nguyên

Hãy bắt đầu với một ví dụ đơn giản: tìm kiếm một số trong một vector các số nguyên.

Giả sử chúng ta có vector sau: { 4, 1, 7, 3, 9, 2, 5, 8, 6 }. Chúng ta muốn tìm số 5.

Nếu dùng tìm kiếm tuyến tính, chúng ta sẽ kiểm tra 4, rồi 1, rồi 7, 3, 9, 2, 5. Mất 7 bước.

Nếu chúng ta sắp xếp vector trước: { 1, 2, 3, 4, 5, 6, 7, 8, 9 }. Bây giờ, để tìm 5:

  1. Kiểm tra phần tử ở giữa: 5. Tìm thấy ngay! Mất 1 bước (trường hợp lý tưởng).
  2. Nếu tìm 2: Kiểm tra giữa (5), 2 nhỏ hơn 5, tìm ở nửa đầu {1, 2, 3, 4}. Kiểm tra giữa của nửa đầu (2.5, lấy 3). 2 nhỏ hơn 3, tìm ở nửa đầu của nửa đầu {1, 2}. Kiểm tra giữa của {1, 2} (lấy 1). 2 lớn hơn 1, tìm ở nửa sau của {1, 2} ({2}). Kiểm tra 2. Tìm thấy! Mất 4 bước.

Rõ ràng, tìm kiếm trên mảng đã sắp xếp hiệu quả hơn nhiều.

C++ cung cấp các hàm tiện lợi trong thư viện <algorithm> để thực hiện cả sắp xếp và tìm kiếm nhị phân.

#include <iostream>
#include <vector>
#include <algorithm> // Bao gồm sort và binary_search

int main() {
    // Dữ liệu ban đầu (không sắp xếp)
    vector<int> numbers = { 4, 1, 7, 3, 9, 2, 5, 8, 6 };

    cout << "Vector ban dau: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // --- Buoc 1: Sap xep vector ---
    // sort sap xep cac phan tu trong khoang tu numbers.begin() den numbers.end()
    // Mac dinh sap xep tang dan cho cac kieu du lieu co the so sanh duoc (nhu int)
    sort(numbers.begin(), numbers.end());

    cout << "Vector sau khi sap xep: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // --- Buoc 2: Tim kiem phan tu tren vector da sap xep ---
    int target = 5;

    // binary_search kiem tra xem target co ton tai trong khoang [begin, end) khong.
    // Chi hoat dong tren du lieu da sap xep!
    // Tra ve true neu tim thay, false neu khong.
    bool found = binary_search(numbers.begin(), numbers.end(), target);

    if (found) {
        cout << "Da tim thay so " << target << " trong vector." << endl;
    } else {
        cout << "Khong tim thay so " << target << " trong vector." << endl;
    }

    // Thu tim kiem mot so khac
    target = 10;
    found = binary_search(numbers.begin(), numbers.end(), target);

    if (found) {
        cout << "Da tim thay so " << target << " trong vector." << endl;
    } else {
        cout << "Khong tim thay so " << target << " trong vector." << endl;
    }

    return 0;
}

Giải thích code:

  1. Chúng ta khai báo một vector<int> chứa các số không theo thứ tự.
  2. Hàm sort(numbers.begin(), numbers.end()); được gọi. Đây là một thuật toán sắp xếp hiệu quả (thường là Introsort, kết hợp QuickSort, HeapSort và InsertionSort) hoạt động trên phạm vi được chỉ định bởi hai iterator (trong trường hợp này là từ đầu đến cuối vector). Sau dòng này, numbers sẽ chứa các phần tử theo thứ tự tăng dần.
  3. Hàm binary_search(numbers.begin(), numbers.end(), target); được sử dụng để kiểm tra xem giá trị target có tồn tại trong vector đã sắp xếp hay không. Nó trả về true nếu tìm thấy và false nếu không. Điều quan trọng là binary_search yêu cầu dữ liệu đầu vào phải được sắp xếp.

Code này minh họa rõ ràng cách bạn sử dụng sort để chuẩn bị dữ liệu, sau đó dùng binary_search để tìm kiếm nhanh chóng.

Ví dụ 2: Kết hợp với các cấu trúc dữ liệu phức tạp hơn

Kỹ thuật này không chỉ áp dụng cho các kiểu dữ liệu cơ bản như số nguyên. Bạn có thể sắp xếp và tìm kiếm các đối tượng phức tạp hơn, miễn là bạn định nghĩa cách so sánh chúng.

Giả sử chúng ta có một danh sách sinh viên, mỗi sinh viên có ID và tên. Chúng ta muốn tìm kiếm sinh viên dựa trên ID.

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

// Dinh nghia cau truc du lieu cho SinhVien
struct SinhVien {
    int id;
    string ten;
};

int main() {
    // Danh sach sinh vien (khong sap xep theo ID)
    vector<SinhVien> danhSachSV = {
        {103, "Nguyen Van A"},
        {101, "Tran Thi B"},
        {105, "Le Van C"},
        {102, "Pham Thu D"},
        {104, "Hoang Van E"}
    };

    cout << "Danh sach SV ban dau:" << endl;
    for (const auto& sv : danhSachSV) {
        cout << "ID: " << sv.id << ", Ten: " << sv.ten << endl;
    }
    cout << endl;

    // --- Buoc 1: Sap xep danh sach theo ID cua sinh vien ---
    // Khi sap xep cac doi tuong custom, chung ta can cung cap mot cach de so sanh chung.
    // O day, chung ta dung lambda function de so sanh hai doi tuong SinhVien dua tren truong 'id'.
    sort(danhSachSV.begin(), danhSachSV.end(),
              [](const SinhVien& a, const SinhVien& b) {
                  return a.id < b.id; // Sap xep tang dan theo ID
              });

    cout << "Danh sach SV sau khi sap xep theo ID:" << endl;
    for (const auto& sv : danhSachSV) {
        cout << "ID: " << sv.id << ", Ten: " << sv.ten << endl;
    }
    cout << endl;

    // --- Buoc 2: Tim kiem sinh vien theo ID tren danh sach da sap xep ---
    int idCanTim = 102;

    // binary_search khong truc tiep lam viec tot voi custom object va chi tra ve true/false.
    // Mot cach tot hon de tim kiem vi tri cua custom object la dung lower_bound.
    // lower_bound tra ve iterator den phan tu dau tien KHONG nho hon gia tri can tim.
    // Chung ta can cung cap comparator de so sanh SinhVien voi ID.
    auto it = lower_bound(danhSachSV.begin(), danhSachSV.end(), idCanTim,
                               [](const SinhVien& sv, int target_id) {
                                   return sv.id < target_id;
                               });

    // Kiem tra xem iterator co hop le (khong phai end()) va phan tu tai vi tri do co dung ID can tim khong.
    // Dieu nay can thiet vi lower_bound tim vi tri co the chen, chu khong chac chan phan tu do ton tai.
    if (it != danhSachSV.end() && it->id == idCanTim) {
        cout << "Da tim thay sinh vien voi ID " << idCanTim << ":" << endl;
        cout << "ID: " << it->id << ", Ten: " << it->ten << endl;
    } else {
        cout << "Khong tim thay sinh vien voi ID " << idCanTim << "." << endl;
    }

    // Thu tim mot ID khong co trong danh sach
    idCanTim = 999;
    it = lower_bound(danhSachSV.begin(), danhSachSV.end(), idCanTim,
                           [](const SinhVien& sv, int target_id) {
                               return sv.id < target_id;
                           });

     if (it != danhSachSV.end() && it->id == idCanTim) {
        cout << "Da tim thay sinh vien voi ID " << idCanTim << ":" << endl;
        cout << "ID: " << it->id << ", Ten: " << it->ten << endl;
    } else {
        cout << "Khong tim thay sinh vien voi ID " << idCanTim << "." << endl;
    }


    return 0;
}

Giải thích code:

  1. Chúng ta định nghĩa một struct SinhVien đơn giản.
  2. vector<SinhVien> lưu trữ danh sách sinh viên.
  3. Khi gọi sort, chúng ta truyền thêm một đối số thứ ba: một lambda function. Lambda này là comparator (hàm so sánh). Nó nhận hai đối tượng SinhVien (a và b) và trả về true nếu a nên đứng trước b trong thứ tự sắp xếp (trong trường hợp này là khi a.id nhỏ hơn b.id).
  4. Để tìm kiếm một đối tượng dựa trên một tiêu chí (như ID), binary_search không còn tiện lợi nữa vì nó yêu cầu bạn phải có một đối tượng SinhVien hoàn chỉnh để so sánh. Thay vào đó, chúng ta sử dụng lower_bound.
  5. lower_bound cũng hoạt động trên dữ liệu đã sắp xếp và sử dụng tìm kiếm nhị phân. Nó tìm kiếm vị trí đầu tiên mà bạn có thể chèn idCanTim vào vector mà vẫn giữ được thứ tự sắp xếp. Nó trả về một iterator đến vị trí đó.
  6. Comparator cho lower_bound hơi khác: nó so sánh một đối tượng trong vector (const SinhVien& sv) với giá trị mà bạn đang tìm kiếm (int target_id). Nó trả về true nếu sv nên đứng trước một phần tử có target_id.
  7. Sau khi có iterator it từ lower_bound, chúng ta cần kiểm tra hai điều:
    • it != danhSachSV.end(): Đảm bảo iterator không trỏ ra ngoài cuối vector (điều này xảy ra nếu giá trị cần tìm lớn hơn tất cả các phần tử).
    • it->id == idCanTim: Đảm bảo rằng phần tử tại vị trí mà lower_bound tìm thấy thực sự có ID mà chúng ta cần. lower_bound chỉ đảm bảo phần tử tại it không nhỏ hơn giá trị tìm kiếm, chứ không đảm bảo nó bằng.
  8. Nếu cả hai điều kiện trên đều đúng, chúng ta đã tìm thấy sinh viên cần. Ngược lại, sinh viên không tồn tại trong danh sách.

Ví dụ này cho thấy tính linh hoạt của việc sử dụng sort và lower_bound (hoặc binary_search) với các kiểu dữ liệu phức tạp, chỉ cần bạn định nghĩa rõ ràng cách so sánh.

Khi nào nên sử dụng kỹ thuật này?

Kỹ thuật sắp xếp rồi tìm kiếm nhị phân rất hữu ích khi:

  • Bạn có một lượng dữ liệu lớn.
  • Bạn cầ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 đó.
  • Bạn có thể chấp nhận chi phí sắp xếp ban đầu.

Các trường hợp điển hình bao gồm:

  • Xây dựng các hệ thống tra cứu nhanh.
  • Xử lý dữ liệu trong cơ sở dữ liệu (các chỉ mục - index - trong database thường được xây dựng dựa trên các cấu trúc dữ liệu đã sắp xếp để tăng tốc độ tìm kiếm).
  • Các bài toán cần kiểm tra sự tồn tại hoặc tìm kiếm vị trí của các phần tử trong tập hợp lớn.

Comments

There are no comments at the moment.