Напишите алгоритм в C стоимости O (log (n)) с подходом разделяй и властвуй

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

Но я понятия не имею, как решить эту проблему с разделением и победить подход. Можно ли решить проблему с помощью модифицированной версии алгоритма быстрой сортировки слиянием?

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]?

• это нечетно? тогда мы должны смотреть на правую сторону, от mid + 1 до n-1

• это четное? у нас есть две возможности:

  • является ли mid-1 допустимым индексом и является ли нечетным [mid-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;
}