2

How to find the maximum and minimum value in an array without using if statement.Are there any built in function in to do so in c++? If not is insertion sort the only way?Thanks in advance.

3
  • is the function allowed to use if statements internally
    – aaronman
    Nov 20, 2013 at 7:40
  • 1
    There are some tricks to do it without branching that would presumably meet your needs. Not for the faint of heart. :) graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax Nov 20, 2013 at 8:27
  • @RetiredNinja's link has examples of branchless conditionals using masks. That's also an approach to vectorize a loop that has a conditional (either manually or done for you by the compiler).
    – Adam
    Nov 20, 2013 at 9:46

2 Answers 2

4

Use std::minmax_element if you use C++11, or std::min_element/std::max_element if no.

std::vector<int> v = {1,2,3,4};
auto minmax = std::minmax_element(v.begin(), v.end());
// now minmax.first points on 1 and minmax.second points on 4

However, if if condition should not be used internally - you can use following thing

template<typename Iterator>
std::pair<Iterator, Iterator> minmax_element(Iterator first, Iterator last)
{
   Iterator min = first, max = first;
   while (first != last)
   {
      min = *min > *first ? first : min;
      max = *max > *first ? max : first;
      ++first;
   }
   return std::make_pair(min, max);
}
3
  • 1
    I'm not sure if his question is just unclear but obviously minmax uses if statements internally, and you can do it without
    – aaronman
    Nov 20, 2013 at 7:36
  • @aaronman Of course it uses if internally, however sort without if statement is also not simple thing.
    – ForEveR
    Nov 20, 2013 at 7:39
  • He didn't say anything about sorting, but it's relatively easy to write a function that does the same thing as minmax, of course I could be totally off on my interpretation of his problem
    – aaronman
    Nov 20, 2013 at 7:40
1

First of all, you can implement function sort(a, b), which returns pair of sorted values. To do it you can use following idea: min(a, b) = (a+b)/2 - |a-b|/2 and max(a, b) = (a+b)/2 + |a-b|/2.

But here you have function |x|=abs(x), which uses 'if' inside. So, we should implement 'abs' without any 'if'. One of the simpliest ways is following: abs(x) = sqrt(x*x) (it is very slow, but it is only an idea). For integer values you can use these approaches: 1, 2, etc.

So, you can implement function sort(a,b) which sorts only pair of values without any 'if'. After it you can use this function to sort the array. After it first element of that sorted array will be minimum value and last element will be maximum element.  

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.