Write an algorithm in C of cost O(log(n)) with divide and conquer approach

user_11569163 0
Viewed 643

I have to write a function in C which takes as input an array and the dimension of the array. We assume that the array has the following characteristics:

  1. Every element in the array is different
  2. the first elements of the array are odd and the remaining are even
  3. There are at least one odd element and one even element in the array

The function has to return the first index of the even elements using a divide and conquer approach and the cost of the algorithm should be O(log(n)).

In a normal case, I would use a function like this:

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

But I have no idea how to solve this problem with the divide and conquer approach. Is it possible to solve the problem using a modified version of the mergesort o quicksort algorithm?

function sorting c arrays algorithm
2 Answers

Think at this: your input is (1,3,5,7,......,2,4,6,8) and its length is n.

Your output will surely not be 0 (you know it is odd) but probably it would not either be the last.

The most important concept behind divide et impera is that is simpler to conquer something which is smaller. So divide you array in two parts and look just at one side, beeing sure that the other part will not contain your result.

Let's suppose that our array (from now on called "a") have indexes from 0 to n-1 (a[n-1] = 8). Let's check at the middle, so first of all we need a index.

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

what is a[mid]?

  • is it odd? then we have to look at the right side, from mid+1 to n-1

  • is it even? we have two possibilities:

    • is mid-1 a valid index and is a[mid-1] odd? then a[mid] is the first even element and mid is the result
    • else look at the left side from 0 to mid-1

then just do it recursively :)

I'm not too used to C so I will write pseudo code

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

You can use a modified binary search to find the index where the even elements start.

At each step, we search either the left or right half of the remaining elements:

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