std::binary_search

#include <algorithm>

// So sánh bằng toán tử <
template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val);

// Sử dụng hàm so sánh tùy chỉnh
template <class ForwardIterator, class T, class Compare>
bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);

Kiểm tra xem một giá trị cho trước có tồn tại trong một phạm vi (range) đã được sắp xếp hay không, sử dụng thuật toán tìm kiếm nhị phân (binary search).

Tham số

`first`

Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi đã sắp xếp cần tìm kiếm.

`last`

Forward Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi. Phạm vi là [first, last).

`val`

Giá trị cần tìm kiếm trong phạm vi.

`comp`

Một hàm hoặc đối tượng hàm (comparator) nhận hai đối số (một phần tử trong phạm vi và val) và trả về true nếu phần tử thứ nhất (trong phạm vi) được coi là nhỏ hơn val theo tiêu chí so sánh, false nếu ngược lại. (Phiên bản 2)

Giá trị trả về

`true`

Nếu giá trị val được tìm thấy trong phạm vi [first, last).

`false`

Nếu giá trị val không được tìm thấy trong phạm vi.

Đặc điểm

Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
binary_search() yêu cầu phạm vi đầu vào đã được sắp xếp theo thứ tự tương ứng (tăng dần hoặc theo comp).
binary_search() chỉ kiểm tra sự tồn tại của giá trị, không trả về vị trí của phần tử. Để tìm vị trí, hãy sử dụng lower_bound() hoặc upper_bound().
binary_search() yêu cầu Forward Iterator, cho phép di chuyển một chiều về phía trước.
Trong C++11 trở lên, bạn có thể sử dụng biểu thức lambda cho hàm so sánh comp (phiên bản 2) để code ngắn gọn và dễ đọc hơn.
binary_search() sử dụng thuật toán tìm kiếm nhị phân (binary search) để tìm kiếm giá trị, do đó, độ phức tạp thời gian là O(log n), trong đó n là số phần tử trong phạm vi.
Phạm vi đầu vào phải được sắp xếp theo thứ tự tăng dần (hoặc theo tiêu chí so sánh được cung cấp) trước khi gọi binary_search(). Nếu phạm vi không được sắp xếp, kết quả sẽ không chính xác.
binary_search() thường được sử dụng để:
- Kiểm tra nhanh sự hiện diện của một phần tử trong một tập hợp dữ liệu đã sắp xếp.
- Xác định xem một giá trị có thuộc một tập hợp đã biết hay không.
- Triển khai các thuật toán và cấu trúc dữ liệu dựa trên tìm kiếm nhị phân.

Phân biệt với lower_bound(), upper_bound(), và equal_range()

lower_bound() trả về iterator trỏ đến phần tử đầu tiên không nhỏ hơn val.
upper_bound() trả về iterator trỏ đến phần tử đầu tiên lớn hơn val.
equal_range() trả về một cặp iterator đại diện cho phạm vi chứa tất cả các phần tử bằng val.
binary_search() chỉ trả về true hoặc false cho biết giá trị có tồn tại hay không.

Ví dụ

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

// Hàm so sánh để tìm kiếm trong dãy giảm dần
bool compareDescending(int a, int b) {
  return a > b; // Lưu ý: Đảo ngược logic so sánh cho dãy giảm dần
}

int main() {
  std::vector<int> numbers = {1, 3, 5, 7, 9};

  // Tìm kiếm số 5 trong numbers (có tồn tại)
  if (std::binary_search(numbers.begin(), numbers.end(), 5)) {
    std::cout << "Found 5 in numbers.\n";
  } else {
    std::cout << "Did not find 5 in numbers.\n";
  }

  // Tìm kiếm số 4 trong numbers (không tồn tại)
  if (std::binary_search(numbers.begin(), numbers.end(), 4)) {
    std::cout << "Found 4 in numbers.\n";
  } else {
    std::cout << "Did not find 4 in numbers.\n";
  }

  std::vector<int> numbers2 = {9, 7, 5, 3, 1};

  // Tìm kiếm số 7 trong numbers2 (đã sắp xếp giảm dần)
  if (std::binary_search(numbers2.begin(), numbers2.end(), 7, compareDescending)) {
    std::cout << "Found 7 in numbers2 (descending).\n";
  } else {
    std::cout << "Did not find 7 in numbers2 (descending).\n";
  }

  return 0;
}

Các hàm liên quan


find	Tìm kiếm phần tử đầu tiên trong một phạm vi có giá trị bằng với một giá trị cho trước
lower_bound	Tìm vị trí đầu tiên trong một phạm vi đã được sắp xếp mà có thể chèn một giá trị cho trước vào mà không làm mất tính sắp xếp của phạm vi
upper_bound	Tìm vị trí đầu tiên trong một phạm vi đã được sắp xếp mà có thể chèn một giá trị cho trước vào mà không làm mất tính sắp xếp của phạm vi, nhưng phải đảm bảo giá trị được chèn vào sau tất cả các phần tử có giá trị bằng với nó
equal_range	Tìm phạm vi con trong một phạm vi đã được sắp xếp mà chứa tất cả các phần tử có giá trị tương đương với một giá trị cho trước

Tham số​

first​

last​

val​

comp​

Giá trị trả về​

true​

false​

Đặc điểm​

Ví dụ​

Các hàm liên quan​