current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

This finds a peak element in an array. Please consider I want only one peak element. Also, my code should follow only C++11/14 and not C++03.

#include <iostream>

int peak(int * arr, size_t size)
{
    auto start = 0;
    auto end = size - 1;

    //empty array
    if(arr == nullptr || size <= 0)
    {
        return -1;
    }

    while(start <= end)
    {
      auto  mid = start + (end - start)/2;
        printf("arr[mid] %d \n",arr[mid]);
        if(start == end)
            return arr[start];

        if(arr[mid] >= arr [mid+1] && arr[mid] >= arr[mid-1])
        {
            return arr[mid];
        }
        else if(arr[mid] < arr[mid-1])
        {
            end = mid;
        }
        else
        {
            start = mid;
        }

    }

    return -1;
}

int main(int argc, const char * argv[]) {
    // insert code here...

    int arr[] = {1,1,8,9,22,2};

    auto elem = peak(arr, sizeof(arr)/sizeof(int)); //Do not understand how to use decaltype instead of int

    printf("%d",elem);

    return 0;
}
share|improve this question
2  
What is the definition of a peak element? –  JS1 23 hours ago
    
@JS1 Not understand your question. –  Pranit Kothari 22 hours ago
    
I don't understand what the program does. What is a "peak" element? Is it an element greater than its two neighbors? How does that definition apply to the first or last element of the array? Is the array assumed in any particular order (e.g. sorted ascending with one rotation)? I don't believe your program works if the array can be in any order. For example, 5 4 3 2 1 7 6. –  JS1 13 hours ago

3 Answers 3

up vote 3 down vote accepted

If you really intend that this be used only on arrays, you can simplify its use somewhat by turning the function into a function template that receives its argument by reference (and since we're making it a template anyway, we might as well make it accept a variety of types, not just int).

template <class T, size_t size>
T peak(const T (&arr)[size]) { 
    // ...

This way you can just pass the array itself, without explicitly passing the size, so the call in main turns into something like this:

int arr[] = {1,1,8,9,22,2};

auto elem = peak(arr);

...and the compiler uses its existing knowledge of the number of elements in arr instead of our having to pass it explicitly (but note that this simply won't work at all for a collection of items allocated with new or malloc--if you try to pass a pointer, the code will be rejected).

The obvious alternative (and possibly a superior one) would be to pass iterators instead. This would let us make this algorithm look and feel a lot more like the others in the standard library. A sub-alternative (so to speak) would be to use a range library (e.g., Eric Neibler's) and pass a range instead of separate iterators.

In keeping with the idea of using a template, I'd also consider changing your conditions so they all use the same comparison operator--traditionally C++ has only required operator< to be defined, and figures everything out from it. In this case it may be more work than it's worth though. It makes no difference for int, but minimizes the interface required by the template, so it can be applied to types that define <, but not any other comparison operators. If you don't anticipate applying it to such types, it may be easier to leave it alone.

I'd also consider renaming some of the variables. I see little gain from using arr instead of array, for one obvious example.

Headers: right now you have #include <iostream>, but you use printf instead of an iostream. I don't see any reason to use printf in this case--I'd use std::cout << elem; instead. If, for whatever reason, you want to continue using printf, include the right header (<cstdio>) instead of <iostream> though.

The one question you've asked is eliminated by turning the code into a template. If, for whatever reason, you decide not to do that, you don't need to use decltype. Rather, to compute the number of elements in an array you typically want to use: (sizeof(arr)/sizeof(arr[0])) (but the template is clearly the better approach).

I'd also prefer to fail loudly, and use some special name for code that checks a pre-condition, such as ensure or requires, so if you did pass a pointer, you'd start the code with something like this:

int peak(int const *array, size_t size) {
    ensure(array != nullptr);
    ensure(size > 0);

...with ensure defined something like this:

#define ensure(cond) (bool(cond) || fputs(#cond, stderr))
share|improve this answer
    
Is T peak(T (&arr)[size]) is C++11 construct, if not what is (&arr), can we not just write arr[size]. –  Pranit Kothari 23 hours ago
    
It's allowed by C++98/03 as well. It passes a reference to an array. No, writing just arr[size] won't accomplish the same thing at all (the parameter type will decay to a pointer, and the size will be lost). –  Jerry Coffin 23 hours ago
    
Great answer. Thank you. Alas! Not sure how much time it will take me to become good C++ developer. –  Pranit Kothari 23 hours ago
    
I definitely agree with the last point, but why come up with the ensure macro when there's assert is the standard lib? –  glampert 12 hours ago
1  
@glampert: A couple of reasons. First, because assert is rarely what you really want (i.e., being disabled in release code). Second, because it's handy to have something specifically for preconditions (and another specifically for post-conditions). –  Jerry Coffin 5 hours ago
up vote 3 down vote

Well you could use non type parameter for size and also a template for a functor (in case you want inverse peaks).

Like this:

template<typename T, typename Func =std::less<T> ,unsigned size>
int peakV2(const T (&arr)[size], Func f = Func())
{   
    auto start = 0;
    auto end = size - 1;

    while(start <= end)
    {
      auto  mid = start + (end - start)/2;
        printf("arr[mid] %d \n",arr[mid]);
        if(start == end) return arr[start];

        if(!f(arr[mid] , arr [mid+1]) && !f(arr[mid] , arr[mid-1]))
        {
            return arr[mid];
        }
        else if(f(arr[mid], arr[mid-1]))
        {
            end = mid;
        }
        else
        {
            start = mid;
        }
    }
    return -1;
}

Another way could be having parameters begin pointer and one past the end, like this

template<typename T, typename Func =std::less<T>>
int peakV3(T* start, T* end, Func f = Func())
{ 
    --end;
    while(start <= end)
    {
      auto  mid = start + (end - start)/2;
        printf("arr[mid] %d \n",*mid);
        if(start == end) return *start;

        if(!f(*mid , *(mid+1)) && !f(*mid , *(mid-1) ))
        {
            return *mid;
        }
        else if(f(*mid, *mid-1))
        {
            end = mid;
        }
        else
        {
            start = mid;
        }
    }
    return -1;
}

This is if you just care about arrays. Otherwise you can have a template that represents a Random access iterator.

Like this:

template<typename RAIterator, typename CMP>
int peakV4(RAIterator start, RAIterator end, CMP f)
{ 
    --end; 
    while(!(end < start))
    {
      auto  mid = start + (end - start)/2;
        printf("arr[mid] %d \n",*mid);

        if(!(start < end || end< start)) return *start;

        if(!f(*mid , *(mid+1)) && !f(*mid , *(mid-1) ))
        {
            return *mid;
        }
        else if(f(*mid, *(mid-1)))
        {
            end = mid;
        }
        else
        {
            start = mid;
        }
    }
    return -1;
}


template<typename RAIterator>
int peakV4(RAIterator start, RAIterator end)
{
    return peakV4(start, end, std::less<decltype(*start)>());
}
share|improve this answer
up vote 3 down vote 
if(arr[mid] >= arr [mid+1] && arr[mid] >= arr[mid-1])

This (and the following conditional) reads outside the bounds of the array if mid is the first or last element (or even both if the array has size 1).

All these direct array manipulations are very C-ish, if you really want to do it "the C++ way", use algorithms. Finding a peak (local maximum) can be handled by existing standard library algorithms just fine. For example:

#include <algorithm>
#include <iostream>
#include <iterator>

int main()
{
  int data[] = { 1,2,3,4,3 };
  auto peak =
      std::adjacent_find(std::begin(data), std::end(data), std::greater<int>());
  if (peak == std::end(data)) {
    // array is sorted in ascending order, reposition to last element
    --peak;
  }
  std::cout << "index: " << std::distance(std::begin(data), peak) << std::endl;
  std::cout << "value: " << *peak << std::endl;
}

(Note: will fail on an empty container. You'll have to guard for that.)

std::begin and std::end were added in C++11, the const versions (std::cbegin) which you could use here if you have a suitable compiler and library are C++14.

share|improve this answer
    
You are proposing an \$O(n)\$ algorithm that solves a different problem than the OP's \$O(\log n)\$ one. –  Jaime 16 hours ago
2  
Not really. The "binary search" implemented by OP isn't appropriate for the problem at hand unless the data is "sorted" in some sense (i.e. there is only one peak, sorted on each side). My solution will find the first local max. I doubt you'll find theoretical complexity differences on random data between the two. –  Mat 15 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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