
C/C++
Помогите с С++! Надо как-то решить задачу с помощью бинарного поиска

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using Vector = std::vector<int>;
template <class Compare>
size_t ternarySearch(const Vector& v, Compare comp) {
size_t l = 0, r = v.size() - 1;
while (r - l > 2) {
const size_t a = l + (r - l) / 3;
const size_t b = r - (r - l) / 3;
if (comp(v[a], v[b]))
r = b;
else
l = a;
}
return std::min_element(v.cbegin() + l, v.cbegin() + r + 1, comp) - v.cbegin();
}
template <class Compare>
int binarySearch(const Vector& v, size_t l, size_t r, int value, Compare comp) {
auto it = std::lower_bound(v.cbegin() + l, v.cbegin() + r, value, comp);
return it == v.cbegin() + r || comp(value, *it) ? -1 : it - v.cbegin();
}
template <class Compare1, class Compare2>
void requestProc(const Vector& v, size_t m, Compare1 less, Compare2 greater) {
const size_t idxExtremum = ternarySearch(v, greater);
for (size_t i = 0; i < m; ++i) {
int query;
std::cin >> query;
int pos = binarySearch(v, 0, idxExtremum, query, less);
if (pos == -1)
pos = binarySearch(v, idxExtremum, v.size(), query, greater);
std::cout << pos << '\n';
}
}
int main() {
size_t n;
std::cin >> n;
Vector v(n);
for (auto& item : v)
std::cin >> item;
size_t m;
std::cin >> m;
if (n > 1) {
if (v[0] < v[1])
requestProc(v, m, std::less<int>(), std::greater<int>());
else
requestProc(v, m, std::greater<int>(), std::less<int>());
} else if (n == 1) {
for (size_t i = 0; i < m; ++i) {
int query;
std::cin >> query;
std::cout << (v[0] == query ? "0\n" : "-1\n");
}
} else {
for (size_t i = 0; i < m; ++i)
std::cout << "-1\n";
}
return 0;
}
#include <vector>
#include <algorithm>
#include <functional>
using Vector = std::vector<int>;
template <class Compare>
size_t ternarySearch(const Vector& v, Compare comp) {
size_t l = 0, r = v.size() - 1;
while (r - l > 2) {
const size_t a = l + (r - l) / 3;
const size_t b = r - (r - l) / 3;
if (comp(v[a], v[b]))
r = b;
else
l = a;
}
return std::min_element(v.cbegin() + l, v.cbegin() + r + 1, comp) - v.cbegin();
}
template <class Compare>
int binarySearch(const Vector& v, size_t l, size_t r, int value, Compare comp) {
auto it = std::lower_bound(v.cbegin() + l, v.cbegin() + r, value, comp);
return it == v.cbegin() + r || comp(value, *it) ? -1 : it - v.cbegin();
}
template <class Compare1, class Compare2>
void requestProc(const Vector& v, size_t m, Compare1 less, Compare2 greater) {
const size_t idxExtremum = ternarySearch(v, greater);
for (size_t i = 0; i < m; ++i) {
int query;
std::cin >> query;
int pos = binarySearch(v, 0, idxExtremum, query, less);
if (pos == -1)
pos = binarySearch(v, idxExtremum, v.size(), query, greater);
std::cout << pos << '\n';
}
}
int main() {
size_t n;
std::cin >> n;
Vector v(n);
for (auto& item : v)
std::cin >> item;
size_t m;
std::cin >> m;
if (n > 1) {
if (v[0] < v[1])
requestProc(v, m, std::less<int>(), std::greater<int>());
else
requestProc(v, m, std::greater<int>(), std::less<int>());
} else if (n == 1) {
for (size_t i = 0; i < m; ++i) {
int query;
std::cin >> query;
std::cout << (v[0] == query ? "0\n" : "-1\n");
}
} else {
for (size_t i = 0; i < m; ++i)
std::cout << "-1\n";
}
return 0;
}
Похожие вопросы
- Помогите решить задачу по программированию на C++
- Помогите решить задачу по C++!
- Помогите решить задачу по программированию
- Помогите решить задачу пожалуйста, в C++
- Помогите пожалуйста решить задачу на языке С#.
- Помогите решить задачу на c++
- Помогите решить задачу на С++ (мне не совсем ясен смысл задания)
- Помогите решить задачу на С++, используя статические массивы
- Товарищи программисты,помогите решить задачу для 1 курса .
- Помогите пожалуйста решить задачу по с++