1 Bối cảnh

Khi làm việc với các mảng đã được sắp xếp (tăng dần hoặc giảm dần), bạn có thường xuyên cần tìm kiếm một phần tử gần với giá trị mục tiêu không? Ví dụ, trong một cấu trúc dữ liệu chứa chuỗi thời gian, bạn cần xác định vị trí của phương tiện của mình hoặc phương tiện khác sau 1 giây.

Với vấn đề nêu trên, bài viết này sẽ giới thiệu một hữu ích: std::lower_bound(). Phương thức này được sử dụng rộng rãi trong các dự án sản xuất, vì vậy tôi muốn chia sẻ với bạn đọc để có thể áp dụng hiệu quả.

2 Giới thiệu về lower_bound

std::lower_bound() là một mẫu hàm trong thư viện chuẩn C++, được định nghĩa trong tệp header <algorithm>. Nó được sử dụng để tìm vị trí của phần tử đầu tiên trong một phạm vi đã sắp xếp mà không nhỏ hơn giá trị cho trước. Hàm này là một triển khai của thuật toán tìm kiếm nhị phân, có thể tìm kiếm hiệu quả một phần tử trong mảng hoặc container đã sắp xếp. Dưới đây là một số đặc điểm chính của std::lower_bound():

• Độ phức tạp thời gian: Với một container có n phần tử, độ phức tạp thời gian của std::lower_bound là O(log n), điều này làm cho nó rất phù hợp cho việc tìm kiếm trên dữ liệu quy mô lớn.
• Tình huống sử dụng: Khi container (như std::vector, std::array hoặc std::deque) đã được sắp xếp và bạn cần tìm kiếm một phần tử hoặc điểm chèn của nó.
• Giá trị trả về: Trả về một iterator, trỏ đến phần tử đầu tiên không nhỏ hơn giá trị cho trước. Nếu tất cả các phần tử đều nhỏ hơn giá trị cho trước, nó sẽ trả về iterator cuối cùng của container.

Nguyên mẫu hàm như sau:

template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

Trong đó, 'first' và 'last' là phạm vi iterator của container, và 'value' là giá trị mục tiêu cần tìm kiếm.

Hàm std::lower_bound() trả về một iterator trỏ đến phần tử đầu tiên trong container không nhỏ hơn giá trị mục tiêu. Nếu giá trị mục tiêu không tồn tại trong container, hàm sẽ trả về một iterator trỏ đến phần tử đầu tiên lớn hơn giá trị mục tiêu.

2.1 Ví dụ đơn giản

Dưới đây là một ví dụ sử dụng hàm std::lower_bound():

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

int main() {
    // Xác định mảng đã sắp xếp
    std::vector<int> data = {2, 4, 6, 8, 10, 12, 14};
    // Giá trị mục tiêu
    int key = 8;
    // Sử dụng std::lower_bound() để tìm giá trị mục tiêu
    auto position = std::lower_bound(data.begin(), data.end(), key);

    if (position != data.end() && *position == key) {
        std::cout << "Giá trị " << key << " được tìm thấy trong container, vị trí: " << std::distance(data.begin(), position) << std::endl;
    } else {
        std::cout << "Giá trị " << key << " không tồn tại trong container" << std::endl;
    }

    return 0;
}

Trong ví dụ trên, chúng ta đã tạo một vector số nguyên đã sắp xếp 'data' và xác định một giá trị mục tiêu 'key'. Sau đó, sử dụng hàm 'std::lower_bound()' để tìm kiếm giá trị mục tiêu trong vector. Nếu tìm thấy giá trị mục tiêu, chương trình sẽ xuất vị trí của nó; ngược lại, chương trình sẽ thông báo rằng giá trị mục tiêu không tồn tại trong container.

2.2 Hàm so sánh tùy chỉnh

Như đã đề cập ở trên, std::lower_bound() cũng giống như std::upper_bound(), cả hai đều hỗ trợ hàm so sánh tùy chỉnh. Để triển khai hàm so sánh tùy chỉnh, bạn chỉ cần nhớ nguyên tắc sau:

**Hàm so sánh tùy chỉnh đều triển khai toán tử "