用"分而治之"的方法在代价为O(log(n))的C中编写一个算法

Question

我必须在C中编写一个函数，该函数将数组和数组的维度作为输入。我们假设阵列具有以下特征：

1. 数组中的每个元素都不同
2. 数组的第一个元素是奇数，其余元素是偶数
3. 数组中至少有一个奇数元素和一个偶数元素

函数必须使用分治方法返回偶数元素的第一个索引，并且算法的代价应该是O(log(n((。

在正常情况下，我会使用这样的函数：

int foo(int v[], int n){
for(int i=0; i<n; i++){
if(v[i]%2==0)
return i; 
}
}

但我不知道如何用分而治之的方法来解决这个问题。有可能使用mergesort o quicksort算法的修改版本来解决这个问题吗？

Answer 1

思考一下：你的输入是(1,3,5,7，…，2,4,6,8(，长度是n。

你的输出肯定不会是0(你知道这很奇怪(，但可能也不会是最后一个。

divide et impera背后最重要的概念是，征服更小的东西更简单。所以把数组分成两部分，只看一边，确保另一部分不会包含结果。

让我们假设我们的数组(从现在起称为"a"(具有从0到n-1(a[n-1]=8(的索引。让我们在中间检查一下，所以首先我们需要一个索引。

int mid = (0 + n-1)/2

什么是【mid】？

• 这奇怪吗？然后我们必须看右边，从中间+1到n-1

• 公平吗？我们有两种可能性：

  • middle 1是有效索引吗？〔middle 1〕是奇数吗？则[mid]是第一个偶数元素，mid是结果
  • 否则从0到1中间看左侧

然后递归执行：(

我不太习惯C，所以我会写伪代码

int exercise(int[] a, int n) {
return exerciseRecursive(a, 0, n-1);
}
int exerciseRecursive(int[] a, int start, int end) {
if (start>end) {
return -1; //there is no even element
}
int mid = (start + end)/2;
if (a[mid]%2==1) { //odd
return exerciseRecursive(a,mid+1,end);
}
else {
if (mid-1>=0 && a[mid-1]%2==1) { //the current element is even and the previous is odd
return mid;
}
else {
return exerciseRecursive(a,start,mid-1);
}


}
}

Answer 2

您可以使用修改后的二进制搜索来查找偶数元素开始的索引。

在每一步中，我们搜索剩余元素的左半部分或右半部分：

int foo(int v[], int n){
int l = 0;
int h = n-1;
while (l < h) {
int m = (l + h) / 2; // `l + h` may overflow, but ignoring that for simplicity...
if (v[m] % 2 != 0) {
l = m + 1; // Search in the left half if `v[m]` is odd.
// Note that the `+ 1` is important to prevent an infinite loop.
} else {
h = m; // Search in the right half if `v[m]` is even.
}
}
return l;
}