CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11
  1. #1
    Join Date
    May 2017
    Posts
    10

    [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

  2. #2
    Join Date
    Jun 2003
    Location
    Armenia, Yerevan
    Posts
    720

    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)).
    Last edited by AvDav; June 5th, 2017 at 02:34 AM.

  3. #3
    Join Date
    Oct 2008
    Posts
    1,456

    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;
        } );
    }
    Last edited by superbonzo; June 5th, 2017 at 03:39 AM.

  4. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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
    Last edited by 2kaud; June 5th, 2017 at 05:46 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  5. #5
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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;
    }
    Last edited by 2kaud; June 5th, 2017 at 08:44 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Best way to find the largest integer value (include duplicate) in an array

    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;
    }
    Last edited by 2kaud; June 5th, 2017 at 05:40 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  7. #7
    Join Date
    May 2017
    Posts
    10

    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

  8. #8
    Join Date
    Feb 2017
    Posts
    677

    Re: Best way to find the largest integer value (include duplicate) in an array

    Quote Originally Posted by netbeansfan View Post
    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).
    Last edited by wolle; June 6th, 2017 at 01:20 AM.

  9. #9
    Join Date
    May 2017
    Posts
    10

    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

  10. #10
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Best way to find the largest integer value (include duplicate) in an array

    Quote Originally Posted by wolle View Post
    - 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 View Post
    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.

  11. #11
    Join Date
    Feb 2017
    Posts
    677

    Re: Best way to find the largest integer value (include duplicate) in an array

    Quote Originally Posted by superbonzo View Post
    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.

    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
    Last edited by wolle; June 10th, 2017 at 01:27 AM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured