查找数组中偶数第一次出现的索引，运行时间为 O(log(n))

Question

我必须实现一个算法，其运行时成本为 O(log(n))，该算法在具有以下属性的数组中找到偶数的第一次出现：

数组第一个元素为奇数，后面的为偶数
我不知道有多少元素是奇数，多少元素是偶数，但我知道至少有1个偶数和1个奇数

我写了这个“草稿代码”，但不能正常工作，有什么改进建议吗？我认为解决方案与我的解决方案没有太大区别（我希望）

    #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;
    }

Answer 1

您遇到的问题是您运行您的 f 方法两次没有条件。此外，您的条件应该是检查您目前正在处理的给定子数组中间的奇偶校验。

你应该做的是这样的：

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);
    }
}

（我没有在这里检查边缘情况等。只是对逻辑的粗略了解）

更新了@marek-r 的评论

Answer 2

存在几个问题：

您没有递归的终止条件。
您递归到数组的两半，破坏了对数复杂性，即使您添加了终止符也是如此。
你的细分方法很神秘；你应该看看中间的元素，然后选择其中的一半。
全局和递归是一个特别不愉快的组合。

这是一个常规的二分搜索，最后有一个小的转折 - 它先递归然后做出决定。

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; 
}

请注意，这使用了传统的半开区间。

Answer 3

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

Answer 4

您有一个包含两个分区的数组，奇数值后跟偶数值。 std::partition_point 标准库算法是您在 O(log n) 时间内找到第二个分区的起点所需的确切函数。

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);
}

本代码基于，只是觉得应该让更多人知道这个略显晦涩的库算法

查找数组中偶数第一次出现的索引，运行时间为 O(log(n))

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

c++

arrays

algorithm

time-complexity