[RESOLVED] Best way to find the largest integer value (include duplicate) in an array
Hi C++ Experts,
I am a novice C++ programmer and have a need to find the largest integer value and index in an array pass into a function. Below is the code that I have come up with but not sure whether there is better way to do this:
Code:
#include <algorithm>
#include <iostream>
using namespace std;
void print_largest_number(int[], int);
int main() {
int arrayNum[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30, 321, 100 };
size_t arraySize = sizeof(arrayNum) / sizeof(arrayNum[0]);
print_largest_number(arrayNum, arraySize);
}
void print_largest_number(int array[], int size)
{
sort(array, array + size);
cout << "The largest value is " << array[size - 1] << endl;
cout << "The array index of largest value is " << size - 1 << endl;
}
However, it fails to check for multiple maximum values & only use the 1st one found. I can do additional comparison on the sorted array to get the correct result but question whether this is a good solution. There are many different ways to achieve the same objectives. In other word, by taking advantage of using built-in sort function, I lose control of locating the initial largest value and having to do additional comparison afterward instead.
Likewise, I will have to find the largest value & index from an array of characters.
Your advice would be appreciated.
Thanks in advance,
George
Re: Best way to find the largest integer value (include duplicate) in an array
Hi, I guess this should help you to find needed value and its position.
Code:
#include <iostream>
using namespace std;
int print_largest_number(int array[], int size)
{
if(size <=0 ) return -1;
int max = array[0], idx = 0;
for(int i = 1; i < size; ++i)
if(max <= array[i]) max = array[i], idx = i;
cout << "The largest value is " << max << endl;
cout << "The array index of largest value is " << idx << endl;
return idx;
}
int main() {
int arrayNum[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30, 321, 100 };
size_t arraySize = sizeof(arrayNum) / sizeof(arrayNum[0]);
print_largest_number(arrayNum, arraySize);
}
Another good idea is to use std::max_element which deals with STL containers' iterators.
And of course this method would take O(N) time complexity instead of O(N*Log(N)).
Re: Best way to find the largest integer value (include duplicate) in an array
an STL c++>=11 version, almost optimally enumerating all largest items for every random access range:
Code:
#include <algorithm>
#include <iostream>
template < typename RAIter >
void print_largest_numbers( RAIter from, RAIter to )
{
for( auto it = std::max_element( from, to ); it != to; it = std::find( std::next(it), to, *it ) )
{
std::cout << "The largest value is " << *it << " at position " << std::distance( from, it ) << std::endl;
}
}
int main()
{
int arrayNum[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30, 321, 100 };
print_largest_numbers( arrayNum, std::end(arrayNum) );
}
BTW, I see that you used array function parameters ( eg. int array[], ... ), FYI keep in mind that array parameters always decays to pointers ( even when a 'size' is specified ) so I hardly see a good reason to use them ...
moreover, if you want to be more generic
Code:
#include <algorithm>
#include <iostream>
template < typename RAIter, typename F >
void for_each_largest_indexed( RAIter from, RAIter to, F fun )
{
for( auto it = std::max_element( from, to ); it != to; it = std::find( std::next(it), to, *it ) )
{
fun( *it, std::distance( from, it ) );
}
}
int main() {
int arrayNum[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30, 321, 100 };
for_each_largest_indexed( arrayNum, std::end(arrayNum), []( auto v, auto i ){
std::cout << "The largest value is " << v << " at position " << i << std::endl;
} );
}
Re: Best way to find the largest integer value (include duplicate) in an array
If you only want to know the maximum value and the position of one element where it occurs then consider using max_element() as mentioned by AvDav in post #2
Code:
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
template<size_t N>
void print_largest_number(const int(&arr)[N])
{
auto l = max_element(begin(arr), end(arr));
if (l != end(arrayNum)) {
cout << "The largest value is " << *l << endl;
cout << "Which occurs at position " << distance(begin(arrayNum), l) << endl;
} else
cout << "No value!" << endl;
}
int main() {
const int arrayNum[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30, 321, 100 };
print_largest_number(arrayNum);
}
However, if you want the positions of all of the maximum values, then this simplistic solution won't do that. To obtain the position of all maximum values, consider
Code:
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
template<size_t N>
void print_largest_number(const int(&arr)[N])
{
auto l = max_element(begin(arr), end(arr));
if (l != end(arr)) {
cout << "The largest value is " << *l << endl;
cout << "Which occurs at positions" << endl;
for (auto a = l; a != end(arr); a = find(next(a), end(arr), *l))
cout << distance(begin(arr), a) << " ";
cout << endl;
} else
cout << "No value!" << endl;
}
int main() {
const int arrayNum[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30, 321, 100 };
print_largest_number(arrayNum);
}
However this requires two passes of the array. This can be done with one pass. I'll work up some example code and post.
PS My post crossed with superbonzo's post #3. He got his in while I was still coding up the example :wave:
Re: Best way to find the largest integer value (include duplicate) in an array
For just one pass of the array, consider
Code:
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
template<size_t N>
void print_largest_number(const int(&arr)[N])
{
vector<size_t> pos{ 0 };
auto maxnum = arr[0];
for (auto it = begin(arr); it != end(arr); ++it) {
if (*it > maxnum) {
pos.clear();
maxnum = *it;
}
if (*it == maxnum)
pos.push_back(distance(begin(arr), it));
}
cout << "Maximum number :" << maxnum << endl;
cout << "Which occurs at" << endl;
for (const auto& l : pos)
cout << l << " ";
cout << endl;
}
int main() {
const int arrayNum[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30, 321, 100 };
print_largest_number(arrayNum);
}
This uses a container (vector in this example) to hold the positions of the current maximum found value. Whether this is a more efficient algorithm will depend upon the number of elements in the array and where the largest value occurs - as when a new largest value is found the container has to be cleared.
The other 'advantage' of doing it this way is that the container can be passed as a function parameter so that the calling routine knows at which locations the largest number occurs. Consider
Code:
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
template<size_t N>
void largest(const int(&arr)[N], vector<size_t>& pos)
{
pos.clear();
pos.push_back(0);
auto maxnum = arr[0];
for (auto it = begin(arr); it != end(arr); ++it) {
if (*it > maxnum) {
pos.clear();
maxnum = *it;
}
if (*it == maxnum)
pos.push_back(distance(begin(arr), it));
}
}
int main() {
const int arrayNum[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30, 321, 100 };
vector<size_t> pos;
largest(arrayNum, pos);
cout << "Maximum: " << arrayNum[pos.front()] << endl;
cout << "Which occurs at" << endl;
for (const auto& l : pos)
cout << l << " ";
cout << endl;
}
Re: Best way to find the largest integer value (include duplicate) in an array
Quote:
Likewise, I will have to find the largest value & index from an array of characters.
as superbonzo indicated in post #3, it is possible to make print_largest_number() more generic so that it works with different types. Consider
Code:
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
template<typename T, size_t N>
void print_largest(const T(&arr)[N])
{
vector<size_t> pos{ 0 };
auto maxnum = arr[0];
for (auto it = begin(arr); it != end(arr); ++it) {
if (*it > maxnum) {
pos.clear();
maxnum = *it;
}
if (*it == maxnum)
pos.push_back(distance(begin(arr), it));
}
cout << "Maximum: " << maxnum << endl;
cout << "Which occurs at" << endl;
for (const auto& l : pos)
cout << l << " ";
cout << endl << endl;
}
int main() {
const int arrayNum[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30, 321, 100 };
print_largest<int>(arrayNum);
const char arrayChar[] = { 'a', 'z', 'c', 'd', 'e', 'f', 'z', 'y' };
print_largest<char>(arrayChar);
}
Or for the previous version without using a container, consider
Code:
template<typename T, size_t N>
void print_largest(const T(&arr)[N])
{
auto l = max_element(begin(arr), end(arr));
if (l != end(arr)) {
cout << "The largest value is " << *l << endl;
cout << "Which occurs at positions" << endl;
for (auto a = l; a != end(arr); a = find(next(a), end(arr), *l))
cout << distance(begin(arr), a) << " ";
cout << endl;
}
else
cout << "No value!" << endl;
}
Re: Best way to find the largest integer value (include duplicate) in an array
Thanks to all those valuable suggestions,
I have used the second last options by 2kaud, which uses container for both integer and character arrays and generate all the maximum values & indices. I will make minor checks to only display the first value & index found easily.
This is the home of C++ Support.
George
Re: Best way to find the largest integer value (include duplicate) in an array
Quote:
Originally Posted by
netbeansfan
I am a novice C++ programmer
In mainstream code an experienced C++ programmer would,
- use an std::vector rather than a C array because it's simpler, safer and makes it straightforward to handle both int and char (and other) sequences using a template parameter,
- make sure to handle the corner case when the sequence is empty,
- use the standard linear way of finding the maximum value of a sequence rather than going for a sort which has higher complexity,
- for simplicity make two sweeps of the sequence, first one to find the maximum and then another one to find the indexes, and only then consider the more complex alternative of doing both in a single sweep (as an optimization if necessary).
You don't have to dig deep into the standard library (using explicit iterators and algorithms) for this. Straightforward programming using only the most basic C++ 11 features would be perfectly fine (and preferable if you ask me).
Re: Best way to find the largest integer value (include duplicate) in an array
Thanks Wolle for your input, I will take this into consideration. George
Re: Best way to find the largest integer value (include duplicate) in an array
Quote:
Originally Posted by
wolle
- for simplicity make two sweeps of the sequence, first one to find the maximum and then another one to find the indexes, and only then consider the more complex alternative of doing both in a single sweep (as an optimization if necessary).
the one or more passes issue is not just about performance, it’s also a design choice related to the kind of ranges the resulting algo is supposed to work with ( eg. input iterators ). Even assuming feasible to copy any input range into a random access buffer, that may not always be possible ( consider an ‘infinite’ input sequence of which you want to accumulate max positions incrementally, for example ).
Quote:
Originally Posted by
wolle
You don't have to dig deep into the standard library (using explicit iterators and algorithms) for this. Straightforward programming using only the most basic C++ 11 features would be perfectly fine (and preferable if you ask me).
this case may be borderline but, generally speaking, I disagree. Using standard algos whenever feasible is always a good idea IMO. A programmer using a naked loop to implement std::max_element() functionality is neither an experienced nor a professional c++ programmer in my opinion.
Re: Best way to find the largest integer value (include duplicate) in an array
Quote:
Originally Posted by
superbonzo
the one or more passes issue is not just about performance, it’s also a design choice
True, but in this case it becomes a performance issue since the design specifies a fixed size sequence. In that case it's reasonable to first consider the two-pass solution (like you did in #3) even though it isn't much additional effort to do it in one pass.
Quote:
this case may be borderline but, generally speaking, I disagree. Using standard algos whenever feasible is always a good idea IMO. A programmer using a naked loop to implement std::max_element() functionality is neither an experienced nor a professional c++ programmer in my opinion.
I think you are a little too categorical here. It certainly is a good idea to consider using a standard library function whenever feasible but to always use one regardless of circumstances is a bad idea. The mere existence of a library function does not guarantee it is the optimal choice. For example some may prefer to use the range-based for-loop even though an STL algorithm is available in order to avoid explicit iterators which they may consider harmful. There is no objective criterion by which this type of a choice can be judged right or wrong. Doing it one way or the other does not define the quality of a programmer.
The use of STL algorithms (in your post #3) avoids some explicit ("naked"?) looping but then the algorithms are used in an explicit loop so you are back on square one. Your loop takes a hopelessly convoluted and error-prone form due to the STL's heavy reliance on explicit iterators so although STL algorithms have great functionality they don't compose well. I use them individually but avoid combining them. Fortunately there is a solution underway called Ranges. It will allow the STL algorithms to finally graduate from the procedural paradigm to the functional, from low-level fiddling with iterators to declarative conceptual coding,
https://www.youtube.com/watch?v=mFUXNMfaciE
