arrays - 用分而治之的方法用 C 语言编写一个成本为 O(log(n)) 的算法

Question

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

数组中的每个元素都不同

数组的第一个元素是奇数，其余元素是偶数

数组中至少有一个奇数元素和一个偶数元素

该函数必须使用分而治之的方法返回偶数元素的第一个索引，并且算法的成本应该是 O(log(n))。
在正常情况下，我会使用这样的函数:

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

但我不知道如何用分而治之的方法解决这个问题。
是否可以使用合并排序 o 快速排序算法的修改版本来解决问题？

Answer 1

想想这个:
你的输入是 (1,3,5,7,......,2,4,6,8) 并且它的长度是 n。
你的输出肯定不会是 0(你知道它是奇怪的)，但它可能不会是最后一个。
分而治之背后最重要的概念是征服较小的东西更简单。因此，将您的数组分为两部分，只看一侧，确保另一部分不会包含您的结果。
假设我们的数组(从现在起称为“a”)的索引从 0 到 n-1 (a[n-1] = 8)。让我们检查中间，所以首先我们需要一个索引。

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

什么是[中]？

奇怪吗？然后我们要看看右边，从mid+1到n-1

是吗？我们有两种可能:

mid-1 是一个有效的索引并且 a[mid-1] 是奇数吗？那么 a[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);
       }
      
       
    }
}