CODEWITHSUNDEEP
c++arraysalgorithmtime-complexity
alexp
alexp

Reputation: 15

Find the index of the first occurrence of even number in the array, with runtime cost O(log(n))

I have to implement an algorithm, with runtime cost of O(log(n)), that find the first occurrence of an even number in an array with these properties:

I've writed this "draft-code", but doesn't work properly, any suggestion to improve it? I consider that solution is not much different from mine (i hope)

    #include <iostream>
    using namespace std;

    int minInd = 1000;

    int f(int v[], int start, int end)
    {
        int m = end/2;

        if(v[start]%2 == 0)
            if(start < minInd) 
                minInd = start;


        f(v,start,m);
        f(v,m+1,end);

        return minInd;
    }


    int main()
    {
        int v[] = {1,3,7,9,5,4,6,8};
        int index = f(v,0,7);
        cout << index << endl;
    }

Upvotes: 1

Views: 676

Answers (4)

Blastfurnace
Blastfurnace

Reputation: 18652

You have an array that contains two partitions, odd values followed by even values. The std::partition_point standard library algorithm is the exact function you need to find the start of the second partition in O(log n) time.

size_t find_first_even(const int *v, int size)
{
    auto itr = std::partition_point(v, v + size, [](int value) { return value & 1; });
    return std::distance(v, itr);
}

This code is based on Marek R's answer, I just think more people should know about this slightly obscure library algorithm.

Upvotes: 0

Marek R
Marek R

Reputation: 38092

size_t find_first_even(const int v[], int size)
{
    return std::distance(v, std::lower_bound(v, v + size, 0,
        [](auto a, auto b) { return a&1 > b&1; }));
}

https://godbolt.org/z/j9jKjn

Upvotes: 0

molbdnilo
molbdnilo

Reputation: 66451

There are several problems:

You don't have a termination condition for the recursion.
You recurse into both halves of the array, destroying the logartihmic complexity even if you add that termination.
Your subdivision method is mysterious; you should look at the element in the middle and then choose one of the halves.
Globals and recursion is a particularly unpleasant combination.

Here's a regular binary search, with a small twist at the end - it recurses first and then makes a decision.

int f(int v[], int start, int end)
{
    // Terminate when nothing is left.
    if (start >= end)
        return -1;
    // Look at the midpoint.
    int mid = start + (end-start) / 2;
    // If it's odd, the first even number is to the right.
    if (v[mid] % 2 != 0)
    {
        return f(v, mid + 1, end);
    }
    // Otherwise, first see if there is any even number to the left.
    int left = f(v, start, mid);
    // And choose a result depending on whether there was.
    return left == -1 ? mid : left; 
}

Note that this uses the conventional half-open intervals.

Upvotes: 1

shapiro yaacov
shapiro yaacov

Reputation: 2346

The issue that you have is that you're running your f method twice with no condition. Also, your condition should be checking the parity of the middle of the given sub-array you're dealing with at the moment.

What you should be doing is something like this:

int f(int v[], int start, int end)
{
    int m = (start + end)/2;


    if(v[m]%2 == 0) {
        if(start == end) { 
            return start;
        } else {
            return f(v, start, m);
        }
    } else {
        return f(v, m, end);
    }
}

(I have not checked for edge cases here etc. Just a rough idea of the logic)

Updated following comment by @marek-r

Upvotes: 0

Related Questions