查找数组中第一次出现偶数的索引，运行时间代价为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

有几个问题:

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

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

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 2

您遇到的问题是您在没有条件的情况下运行了两次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 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);
}

这段代码是基于Marek R的回答，我只是觉得应该让更多的人知道这个稍微晦涩的库算法。