1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// <algorithm>
10
11// template<ForwardIterator Iter, class T>
12// constexpr bool // constexpr after C++17
13// binary_search(Iter first, Iter last, const T& value);
14
15#include <algorithm>
16#include <vector>
17#include <cassert>
18#include <cstddef>
19
20#include "test_macros.h"
21#include "test_iterators.h"
22
23#if TEST_STD_VER > 17
24TEST_CONSTEXPR bool lt(int a, int b) { return a < b; }
25
26TEST_CONSTEXPR bool test_constexpr() {
27 int ia[] = {1, 3, 3, 6, 7};
28
29 return std::binary_search(std::begin(ia), std::end(ia), 1)
30 && std::binary_search(std::begin(ia), std::end(ia), 3)
31 && !std::binary_search(std::begin(ia), std::end(ia), 9)
32 ;
33 }
34#endif
35
36template <class Iter, class T>
37void
38test(Iter first, Iter last, const T& value, bool x)
39{
40 assert(std::binary_search(first, last, value) == x);
41}
42
43template <class Iter>
44void
45test()
46{
47 const unsigned N = 1000;
48 const int M = 10;
49 std::vector<int> v(N);
50 int x = 0;
51 for (std::size_t i = 0; i < v.size(); ++i)
52 {
53 v[i] = x;
54 if (++x == M)
55 x = 0;
56 }
57 std::sort(first: v.begin(), last: v.end());
58 for (x = 0; x < M; ++x)
59 test(Iter(v.data()), Iter(v.data()+v.size()), x, true);
60 test(Iter(v.data()), Iter(v.data()+v.size()), -1, false);
61 test(Iter(v.data()), Iter(v.data()+v.size()), M, false);
62}
63
64int main(int, char**)
65{
66 int d[] = {0, 2, 4, 6};
67 for (int* e = d; e <= d+4; ++e)
68 for (int x = -1; x <= 7; ++x)
69 test(first: d, last: e, value: x, x: (x % 2 == 0) && ((e-d)*2 > x));
70
71 test<forward_iterator<const int*> >();
72 test<bidirectional_iterator<const int*> >();
73 test<random_access_iterator<const int*> >();
74 test<const int*>();
75
76#if TEST_STD_VER > 17
77 static_assert(test_constexpr());
78#endif
79
80 return 0;
81}
82

source code of libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/binary_search.pass.cpp