Форум программистов, компьютерный форум CyberForum.ru

lower/upper bound - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.93
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,693
02.03.2013, 14:36     lower/upper bound #1
добрый день. имеется массив a, число x. найти такое i, что |ai - x| минимально, ну т.е.
a = {-10, -4, 8, 10}, x = 5 -> i = 1
бин поиск можно написать, но как с помощью stl? там можно в lower/upper bound четвертым аргументом передавать компаратор, но как его описать? у меня не получается) спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
02.03.2013, 14:59     lower/upper bound #2
в вашем случае подходящий элемент - восьмерка. использовать нужно скорее std::min_element с предикатом.
с бустом или с новым стандартом это будет менее многословно чем по олдскульному. вот олдскульный вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <iostream>
 
class Pred
{
    int m_x;
 
public:
    Pred(int x)
        : m_x(x)
    {
    }
 
    bool operator () (int lhs, int rhs) const
    {
        return abs(lhs - m_x) < abs(rhs - m_x);
    }
};
 
int main()
{
    int a[] = {-10, -4, 8, 10};
    const int x = 5;
    const unsigned arraySize = sizeof(a) / sizeof(*a);
    int* minA = std::min_element(a, a + arraySize, Pred(x));
    const unsigned minAindex = std::distance(a, minA);
    std::cout << "min(|ai - " << x << "|) = " << "a[" << minAindex << "] = " << a[minAindex] << std::endl;
 
    return 0;
}
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,693
02.03.2013, 18:23  [ТС]     lower/upper bound #3
да, точно, восьмерка. мне бы не надо за логарифм искать, а не за линию.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
02.03.2013, 18:35     lower/upper bound #4
чтобы так чтобы lower_bound заюзать нужно, чтобы элементы в массиве были отсортированы по нужному критерию. если это не подходит - то курить другие алгоритмы поиска, о которых я не знаю.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,693
02.03.2013, 20:36  [ТС]     lower/upper bound #5
элементы отсортированы в порядке возрастания. ну ладно, тогда так бин поиск накидать нужно ) спасибо.
Yandex
Объявления
02.03.2013, 20:36     lower/upper bound
Ответ Создать тему
Опции темы

Текущее время: 13:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru