Identifying first negative number in array of doubles

Question

I was asked to create a function that checks if an array of doubles has all negative numbers or none. If these 2 (all negative, all positive) are false, check the first negative number, using recursion and only using built-in C++ features.

int first_negative(const double val [] , unsigned array, unsigned short instance_ = 0) //Dont change instance!
{
    //None negative?
    bool none_negative;
    for(int i = 0; i < array; i++)
    {
        if(val[i] > 0) none_negative = true;
        else
        {
            none_negative = false;
            break;
        }
    }
    if(none_negative) return 0;

    //All negative?
    bool negative_instance;
    for(int i = 0; i < array; i++)
    {
        if(val[i] < 0) negative_instance = true;
        else
        {
            negative_instance = false;
            break;
        }
    }


    //Never change instance!
    static short instance = instance_;
    if(array < 1) return 0;
    if(val[instance] < 0) return instance;
    instance++;
    return first_negative(val, array, instance);
}

Can I make it better? Can I remove the instance parameter?

You probably have a bug since you use none_negative == true as assignment, when it is not... — Uri Agassi, 4 hours ago

Jamal · Accepted Answer · 2014-02-10 17:14:55Z

up vote 6 down vote accepted

I believe the parameter names val and array are switched around. An array shouldn't be a single variable, and a value shouldn't be an array. Otherwise, the names themselves are okay.
It's preferred to index through a C-style array with an std::size_t, especially if the array size is larger than an int. This could be helpful if you'll be working with very large numbers, although the recursion aspect here may render that unlikely. Even if you're not, it's best to develop that habit.
This looks a bit misleading:
```
if(val[instance] < 0) return instance;
instance++;
```
At first, I thought the instance++ was missing indentation and belonged to the if statement. To make this clearer, you could separate the two lines or, even better, have curly braces for the if statement. The latter also helps with better maintainability.
```
if (val[instance] < 0)
{
    return instance;
}

instance++;
```
Again, some of the naming is misleading:
```
if(array < 1) return 0;
```
From a glance, that just looks incorrect as you cannot check an array like that. Proper naming is very important, even for a small program like this.

edited 3 hours ago

answered 4 hours ago

Jamal♦
5,17532355

Yep, I already use containers. This challenge was creating algorithm only built-in C++ features. – Lucas Henrique 4 hours ago

Array is from 0 to "array", scan from the first value, with the "array" delimiter. – Lucas Henrique 4 hours ago

@LucasHenrique: That's fine. I can remove the second bulletpoint. – Jamal♦ 4 hours ago

So, my code, can be better? (With the requirements) – Lucas Henrique 4 hours ago

@LucasHenrique: I'll take a better look at it later. It looks like rolfl has more to say now. – Jamal♦ 4 hours ago

show 3 more comments

gnasher729 · Answer 2 · 2014-02-10 19:02:03Z

I thought "negative" means "less than zero" and "positive" means "greater than zero", with zero being neither positive nor negative. So if all array elements are zero, they are not all positive, not all negative, and there is no first negative element. If the array has no elements at all, then they are all positive and at the same time all negative. So the specification for the function is a bit on the weak side.

Usually you use "non-negative" for "positive or zero". If you meant "Positive or zero" when writing "positive" that should be checked.

Jamal · Answer 3 · 2014-02-10 17:35:39Z

This sounds artificial to me. Why the mundane/recursive requirements?

To check if all values are positive, or negative, you have to scan all of the doubles.

While you are doing that, you may as well identify which member is the first negative.

Doing it all in combination would result in an O(n) operation that is small, and as fast as it could possibly be (unless you have things like sorted data).

So, create a DoubleDetails class that takes an array of double as a parameter, scan the entire array, and save away the first negative, and two bools, whether it is all positive, or all negative.

Then have methods that you can call on the class that return:

allpositive() - true if they are all positive
allnegative() - true if all negative.
firstnegative() - the first negative value (if !allpositive && !allnegative).

tinstaafl · Answer 4 · 2014-02-10 17:29:00Z

You might be missing the point of recursion. Basically recursion replaces a loop. So, in your case, it doesn't make much sense to have the loop(s) inside the function. See if something like this works:

int FirstNeg(const double dblearray[], size_t size, int firstnegindex = -1, unsigned int index = 0, bool allpos = true, bool allneg = true)
{
    if((int)size == index)
    {
        if(allpos || allneg)
            firstnegindex = -1;
        return firstnegindex;
    }
    if(firstnegindex == -1 && dblearray[index] < 0)
        firstnegindex = index;
    if(allpos && dblearray[index] < 0)
        allpos = false;
    if(allneg && dblearray[index] >= 0)
        allneg = false;
    return FirstNeg(dblearray,size,firstnegindex,++index,allpos,allneg);
}

This will return a -1 if the array is all negative or all positive. I used an array but this should work for any indexed container.

Your call to the function only needs to include the array and the size assuming you are starting at index 0.

Kexlox · Answer 5 · 2014-02-10 20:31:19Z

I started with tinstaafl's answer, but modified it a bit to short circuit as soon as we know the answer:

int FirstNeg(const double dblearray[], size_t size, int firstnegindex = -1, unsigned int index = 0, bool haspos = false, bool hasneg = false)
{
    if((int)size == index)
        return -1;
    if(!hasneg && dblearray[index] < 0) {
        firstnegindex = index;
        hasneg = true;
    }
    if(!haspos && dblearray[index] >= 0)
        haspos = true;
    if (haspos && hasneg)
        return firstnegindex;   
    return FirstNeg(dblearray,size,firstnegindex,++index,haspos,hasneg);
}

asked	today
viewed	258 times
active	today

current community

more stack exchange communities

Identifying first negative number in array of doubles

5 Answers

Your Answer

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

Hot Network Questions

current community

more stack exchange communities

Identifying first negative number in array of doubles

5 Answers

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions