Задача

Написати функцію яка знаходить значення у двомірному масиві з відсортованими рядками і стовпцями швидше ніж простим перебором елементів.

Рішення

Головний трюк полягає в тому щоб не шукати з першого елемента першого рядка (лівого верхнього кута): у такому разі важко визначитися в який бік рухатися якщо поточний елемент менший за той що шукаємо – вправо чи вниз.

Якщо ж ми почнемо з лівого нижнього чи правого верхнього кута то кожного разу обираючи напрямок руху можемо відсікати цілий рядок чи стовбець.

Почнемо шукати з першого рядка і останнього елемента. Якщо поточний елемент менше за значення яке ми шукаємо то збільшуємо номер рядка, інакше (якщо елемент менше) – зменшуємо колонку. Повторюємо доки не знайдемо елемент або не дійдемо до краю масиву.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
bool find_element(int** a, int m, int n, int val) 
{ 
    for (int row = 0, col = n - 1; row < m && col >= 0; ) 
    { 
        int &elem = a[row][col]; 
        if (val == elem) 
        { 
            return true; 
        } 
        else if (val < elem) 
        { 
            --col; 
        } 
        else 
        { 
            ++row; 
        } 
    } 

    return false; 
} 

Задача

Написати функцію яка зливає 2 відсортовані масиви. Перший масив має розмір достатній для того щоб у ньому помістилися елементи обох масивів (тобто функції передається не повний розмір першого масиву, а лише кількість відсортованих елементів які треба використати).

Додаткову пам’ять не використовувати.

Рішення

Почнемо запловнювати результуючий масив з кінця:

  1. Встановити поточні індекси обох масивів на останні елементи, а індикс запису на позицію в якій має бути останній елемент злитого масиву.
  2. Якщо індекс хоч для одного з масивів добіг нуля переходимо до кроку 5.
  3. Вибираємо з двох елементів найбільший і записуємо його у позицію на яку вказує індекс запису. Зменшуємо індекси запису і індекс читання для того масива з якого скопіювали елемент.
  4. Переходимо до кроку 2.
  5. Для Другого масива копіюємо ті елементи що залишилися – очевидно що якщо залишилися незкопійовані елементи у першому масиві то вони просто стануть на те саме місце де вони є зараз.
void merge_two_sorted_arrays(int *a, int m, int *b, int n) { int k = m + n - 1; int i = m - 1; int j = n - 1; while (i >= 0 && j >= 0) { if (a[i] > b[j]) { a[k--] = a[i--]; } else { a[k--] = b[j--]; } } for (; j >= 0; a[k--] = b[j--]); }