Lower number/bound

[temper3243]

Hi,

If i have an array like {1,4, 10, 15 , 20 , 30 } of size n , now if i
want to search for number

25 , i should get 20 , if i search for number 11 i hould get 10 , if i
search for 4 i should get 4, if i search for a number and it doesn't
exist i should get the lower number between which it lies. All numbers
are bound to lie between 1 and n.

Can you tell me a easy way to do it.

Does STL have anything for this.

Regards
Nik

[Mike Wahler]

<te********@gmail.com> wrote in message
news:11*********************@j73g2000cwa.googlegro ups.com...

Hi,

If i have an array like {1,4, 10, 15 , 20 , 30 } of size n , now if i
want to search for number

25 , i should get 20 , if i search for number 11 i hould get 10 , if i
search for 4 i should get 4, if i search for a number and it doesn't
exist i should get the lower number between which it lies. All numbers
are bound to lie between 1 and n.

Can you tell me a easy way to do it.

Does STL have anything for this.

It has something close to it: <algorithm> has std::upper_bound
and std::lower_bound for sequence containers, and std::map,
std::multimap, std::set, and std::multiset types have member
functions 'upper_bound' and 'lower_bound'. But these functions
return iterators, not values. The map and set member functions
return iterators to existing elements, while the 'standalone'
functions used with sequence containers return iterators to
where the searched value would be inserted with existing ordering
preserved (default ordering with operator<, or specified with
a predicate. I'm not sure I stated that exactly accuratedly,
so look this stuff up to be sure.

A great book about the C++ standard library is:
www.josuttis.com/libbook

-Mike

[Shimon Shvartsbroit]

This can be very easily accomplished if you make sure the array is
sorted in ascending order, as it is in your example.

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

void main()
{
typedef std::vector<int> MyArray;

int tmp[] = {1,4, 10, 15 , 20 , 30 };

MyArray arr(tmp, tmp + sizeof(tmp) / sizeof(tmp[0]));

// sort in asecnding order, in case it's not sorted
std::sort(arr.begin(), arr.end());

// find the first value that is less or equal to 25.. the search is
done from the end of container to its begining
MyArray::reverse_iterator it = std::find_if(arr.rbegin(), arr.rend(),
std::bind2nd(std::less_equal<int>(), 25));

if (it!=arr.rend())
{
// here is the value of the found item
std::cout << *it << std::endl;
}
}

lower_bound and upper_bound won't do in this case. But hey, it's so
easy to use predicates in STL algorithms :-)

[Jack Saalweachter]

Shimon Shvartsbroit wrote:

This can be very easily accomplished if you make sure the array is
sorted in ascending order, as it is in your example.

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

void main()
{
typedef std::vector<int> MyArray;

int tmp[] = {1,4, 10, 15 , 20 , 30 };

MyArray arr(tmp, tmp + sizeof(tmp) / sizeof(tmp[0]));

// sort in asecnding order, in case it's not sorted
std::sort(arr.begin(), arr.end());

// find the first value that is less or equal to 25.. the search is
done from the end of container to its begining
MyArray::reverse_iterator it = std::find_if(arr.rbegin(), arr.rend(),
std::bind2nd(std::less_equal<int>(), 25));

if (it!=arr.rend())
{
// here is the value of the found item
std::cout << *it << std::endl;
}
}

lower_bound and upper_bound won't do in this case. But hey, it's so
easy to use predicates in STL algorithms :-)

While the question "Why aren't you using vectors?" is valid, it is worth
noting, in my opinion, that pointers themselves can act as iterators and
be passed directly to the standard algorithms.

int tmp[] = {1, 4, 10, 15, 20, 30};
unsigned int size = 6; // size of the array

std::sort(tmp, tmp + size);
int *val = std::upper_bound(tmp, tmp + size, 25);

Jack Saalweachter

[Stuart Golodetz]

<te********@gmail.com> wrote in message
news:11*********************@j73g2000cwa.googlegro ups.com...

Hi,

If i have an array like {1,4, 10, 15 , 20 , 30 } of size n , now if i
want to search for number

25 , i should get 20 , if i search for number 11 i hould get 10 , if i
search for 4 i should get 4, if i search for a number and it doesn't
exist i should get the lower number between which it lies. All numbers
are bound to lie between 1 and n.
Possibly a pedantic observation, but in the above array, doesn't n = 6? Only
1 and 4 lie between 1 and n in the above array. (Actually, 1 may not either,
it depends how we define "between".) With the bounds given, it's difficult
to know what to return for the following example (say):

[2,2,3,3] (then all the array elements lie between 1 and 4, however you
define "between")

Searching for 1 is expected to give result what?

Regards,
Stu
Can you tell me a easy way to do it.

Does STL have anything for this.

Regards
Nik