Въведение в Линейните Структури от Данни: Масиви, Свойства, Обектно-Ориентирана Реализация и Двоично Търсене в C++

▶⚡ Накратко

За Изпита

🎯Учебни Цели

След края на тази лекция вие ще можете да:

• ✓Разберете концепцията за линейни структури от данни, особено масивите
• ✓Опишете основните свойства на масивите
• ✓Имплементирайте масиви с обектно-ориентирани техники в C++
• ✓Обяснете и реализирайте двоично търсене върху сортирани масиви в C++
• ✓Анализирайте приложението и ограниченията на масивите и двоичното търсене

---

1. Въведение в Структурите от Данни и Масивите

Какво са Структурите от Данни?

💡Защо са важни структурите от данни?

Структурата от данни е организиран формат за съхранение и управление на данни, който позволява на програмистите ефективно да достъпват и манипулират информация. В компютърните науки става въпрос за избора на правилния начин за организиране на данните, така че операции като съхранение, извличане и манипулация да бъдат възможно най-ефективни.

Важността на структурите от данни в програмирането не може да бъде надценена. Те позволяват ефективно съхранение, извличане и манипулация на данни, а правилното им използване пряко подобрява производителността на софтуерните приложения.

ℹ️Структури от данни и алгоритми

Структурите от данни комбинират примитивни типове данни (като integers, characters, booleans) в свързани формати, които позволяват операции от по-високо ниво като сортиране, търсене, вмъкване и изтриване.

Тази комбинация от структури от данни и алгоритми (DSA) помага да се решат два фундаментални предизвикателства:

• Времева сложност: Колко време отнема на алгоритъм да завърши въз основа на размера на входа
• Пространствена сложност: Колко памет използва алгоритъм въз основа на размера на входа

Линейни Структури от Данни и Масиви

ℹ️Какво е линейна структура от данни?

Линейните структури от данни представляват фундаментална категория организация на данни, при която елементите са подредени последователно или линейно, като всеки елемент е логически свързан с предходния и следващия си елемент.

Масивите са най-простият и фундаментален тип линейна структура от данни. Масивът е непрекъснат блок от памет, който съхранява множество елементи от един и същи тип в последователност.

Характеристики на Масива

• Непрекъснато разпределение на паметта
• Хомогенни елементи (един тип)
• Константен достъп O(1) по индекс
• Фиксиран размер при създаване

Предимства

• Бърз достъп до произволен елемент
• Просто изпълнение
• Ефективно използване на кеша
• Предсказуемо поведение

Всеки елемент в масива може да бъде достъпен директно чрез неговата индексна позиция. Тази структурна простота, комбинирана с изчислителна ефективност, прави масивите основен строителен блок за по-сложни приложения.

---

2. Свойства на Масивите

2.1. Непрекъснато Разпределение на Паметта

ℹ️Непрекъснато Разпределение

Масивите съхраняват елементите си в непрекъснати места в паметта. Това означава, че всеки елемент е поставен последователно в паметта без празнини между тях.

Това фундаментално свойство има значителни последствия за производителността и ефективността на паметта:

Директно изчисляване на адрес:

Тъй като всички елементи са от един и същи тип и заемат еднакво количество памет, адресът на всеки елемент може да бъде изчислен директно:

адрес = базов_адрес + (индекс × размер_на_елемента)

✅Предимства на непрекъснатото разпределение

• Бърз достъп: Не е нужно да обхождаме елементи - можем да скочим директно до желания
• Кеш локалност: Процесорът може ефективно да зарежда блокове памет в кеша
• Без фрагментация: Целият масив заема един единен блок памет

2.2. Фиксиран Размер и Хомогенни Елементи

ℹ️Характеристики

Масивите имат фиксиран размер и съдържат хомогенни елементи (всички елементи трябва да са от един тип данни).

Фиксиран размер:

След като масивът е създаден с определена дължина, тази дължина не може да бъде променена по време на изпълнение на програмата.

✅ Предимства

• Предсказуемост при заделяне на памет
• Без overhead за динамично преоразмеряване
• Ефективно използване на паметта

⚠️ Ограничения

• Нужда от предварително планиране
• Скъпо преоразмеряване (създаване на нов масив)
• Може да води до загуба на памет

Хомогенни елементи:

Всички стойности в масива трябва да са от един тип - например всички integers, всички floating-point числа, или всички обекти от определен клас.

int numbers[5] = {10, 20, 30, 40, 50};     // ✅ Валидно
double prices[3] = {9.99, 15.50, 22.00};   // ✅ Валидно
// int mixed[3] = {10, 20.5, "text"};      // ❌ Невалидно

✅Защо е важна хомогенността?

• Гарантира, че всеки елемент заема идентично пространство в паметта
• Предпоставка за ефективното индексно адресиране
• Опростява управлението на паметта и проверката на типовете

2.3. Константен Достъп по Индекс

ℹ️O(1) Достъп

Едно от най-мощните свойства на масивите е, че достъпът до всеки елемент отнема константно време, означено като O(1) в Big O нотация.

Моментално извличане:

Тъй като компютърът може да изчисли адреса на всеки елемент, използвайки формулата, която дискутирахме, извличането на елемент на всяка позиция е моментално и независимо от размера на масива.

❌

Свързан Списък - O(n)

За достъп до n-тия елемент трябва да обходим n-1 предходни елемента.
За масив с 10,000 елемента: до 10,000 стъпки

✅

Масив - O(1)

Директно изчисляване на адрес и един достъп до паметта.
За масив с 10,000 елемента: 1 стъпка

Практическо значение:

✅Приложения за критични към производителността системи

• Системи в реално време
• Обработка на графика
• Научни изчисления
• Всяко приложение, където забавянията на милисекундно ниво имат значение

---

3. Обектно-Ориентирана Реализация на Масиви в C++

3.1. C++ Основи: Статични Масиви и Класове

Синтаксис за статични масиви в C++:

типДанни имеМасив[размер];

ℹ️Компоненти на декларация

• типДанни: Типът елементи, които ще съдържа масивът (напр. int, string, double)
• имеМасив: Името, което давате на масива
• размер: Константно цяло число, указващо броя на елементите

Примери:

#include <iostream>
#include <string>

int main() {
    // Декларация и инициализация на масив от 5 integers
    int numbers[5] = {10, 20, 30, 40, 50};

    // Декларация на масив от 4 strings
    std::string cars[4] = {"Volvo", "BMW", "Ford", "Mazda"};

    // Декларация на неинициализиран масив
    float grades[10]; // Стойностите са неинициализирани

    // Достъп до елементи чрез индекс (базиран на 0)
    std::cout << "Първо число: " << numbers[0] << std::endl;
    std::cout << "Трета кола: " << cars[2] << std::endl;

    // Обхождане на масива
    std::cout << "Всички числа: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << numbers[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Въведение в Класове и Обектно-Ориентирана Инкапсулация:

ℹ️Какво е клас?

В C++, класът е чертеж за създаване на обекти. Той инкапсулира данни (атрибути) и функции (методи), които оперират върху тези данни. Това е основата на Обектно-Ориентираното Програмиране (ООП).

#include <iostream>

class BasicArrayWrapper {
private:
    int data[10];      // C-style масив като частен член
    int currentSize;   // Следи броя на текущо използваните елементи

public:
    // Конструктор: Инициализира обекта
    BasicArrayWrapper() : currentSize(0) {
        for (int i = 0; i < 10; ++i) {
            data[i] = 0;
        }
        std::cout << "BasicArrayWrapper създаден!" << std::endl;
    }

    // Метод за добавяне на елемент в края
    void add(int value) {
        if (currentSize < 10) {
            data[currentSize++] = value;
        } else {
            std::cout << "Масивът е пълен!" << std::endl;
        }
    }

    // Метод за получаване на елемент по индекс
    int get(int index) const {
        if (index >= 0 && index < currentSize) {
            return data[index];
        }
        std::cout << "Грешка: Индекс извън границите!" << std::endl;
        return -1;
    }

    // Метод за отпечатване на всички елементи
    void print() const {
        std::cout << "Елементи: [";
        for (int i = 0; i < currentSize; ++i) {
            std::cout << data[i];
            if (i < currentSize - 1) std::cout << ", ";
        }
        std::cout << "]" << std::endl;
    }

    int size() const { return currentSize; }
};

✅Ключови точки за инкапсулацията

• Скриване на данни: Вътрешният масив (data) и неговият размер (currentSize) са private
• Контролиран достъп: Достъпът се осъществява само чрез публични методи
• Защита: Проверка на границите предотвратява невалиден достъп до паметта

3.2. Проектиране на Прост Клас за Масив

По-робустен Array клас в C++ обикновено включва динамично заделяне на памет:

#include <iostream>
#include <stdexcept>

template <typename T>
class CustomArray {
private:
    T* data;         // Указател към динамично заделен масив
    size_t capacity; // Максимален брой елементи

public:
    // Конструктор
    CustomArray(size_t n) : capacity(n) {
        if (n == 0) {
            data = nullptr;
        } else {
            data = new T[capacity];
            for (size_t i = 0; i < capacity; ++i) {
                data[i] = T(); // Инициализация по подразбиране
            }
        }
    }

    // Деструктор
    ~CustomArray() {
        delete[] data;
        data = nullptr;
    }

    // Copy Constructor
    CustomArray(const CustomArray& other) : capacity(other.capacity) {
        data = new T[capacity];
        for (size_t i = 0; i < capacity; ++i) {
            data[i] = other.data[i];
        }
    }

    // Assignment Operator
    CustomArray& operator=(const CustomArray& other) {
        if (this != &other) {
            delete[] data;
            capacity = other.capacity;
            data = new T[capacity];
            for (size_t i = 0; i < capacity; ++i) {
                data[i] = other.data[i];
            }
        }
        return *this;
    }

    // Достъп до елемент (безопасен)
    T get(size_t index) const {
        if (index >= capacity) {
            throw std::out_of_range("Индекс извън границите!");
        }
        return data[index];
    }

    // Модификация на елемент (безопасен)
    void set(size_t index, const T& value) {
        if (index >= capacity) {
            throw std::out_of_range("Индекс извън границите!");
        }
        data[index] = value;
    }

    // Препокриване на оператор []
    T& operator[](size_t index) {
        if (index >= capacity) {
            throw std::out_of_range("Индекс извън границите!");
        }
        return data[index];
    }

    const T& operator[](size_t index) const {
        if (index >= capacity) {
            throw std::out_of_range("Индекс извън границите!");
        }
        return data[index];
    }

    size_t getSize() const { return capacity; }

    void print() const {
        std::cout << "[";
        for (size_t i = 0; i < capacity; ++i) {
            std::cout << data[i];
            if (i < capacity - 1) std::cout << ", ";
        }
        std::cout << "]" << std::endl;
    }
};

⚠️Важни аспекти на управлението на паметта

Деструкторът е от ключово значение! Той освобождава динамично заделената памет, когато обектът бъде унищожен, предотвратявайки изтичане на памет.

Copy Constructor и Assignment Operator осигуряват дълбоко копиране, което е необходимо за правилно управление на динамичната памет.

int main() {
    try {
        CustomArray<int> arr(5);
        arr.print(); // [0, 0, 0, 0, 0]

        // Задаване на стойности
        for (size_t i = 0; i < arr.getSize(); ++i) {
            arr.set(i, (i + 1) * 10);
        }
        arr.print(); // [10, 20, 30, 40, 50]

        // Достъп чрез operator[]
        arr[0] = 5;
        std::cout << "Променен елемент на индекс 0: " << arr[0] << std::endl;

        // Дълбоко копиране
        CustomArray<int> arr2 = arr;
        arr2[1] = 25;
        arr2.print(); // [5, 25, 30, 40, 50]
        arr.print();  // [5, 20, 30, 40, 50] - оригиналът е непроменен

    } catch (const std::out_of_range& e) {
        std::cerr << "Хваната грешка: " << e.what() << std::endl;
    }

    return 0;
}

---

4. Алгоритъм за Двоично Търсене

4.1. Мотивация за Двоично Търсене

💡Защо двоично търсене?

Представете си, че търсите определена дума във физически речник. Няма да започнете от първата страница и да сканирате всяка дума. Вместо това бихте отворили приблизително в средата, видели къде се намирате азбучно и решили дали думата ви е в първата или втората половина. След това бихте повторили този процес, бързо стеснявайки търсенето.

Това е същността на двоичното търсене!

Сценарии за приложение:

• Търсене на конкретен запис в голяма база данни
• Намиране на страница в сортиран индекс
• Локализиране на елемент в списък със сортирани цени

Линейно Търсене O(n)

За 1,000,000 елемента:

• Максимум: 1,000,000 сравнения
• Средно: 500,000 сравнения

Двоично Търсене O(log n)

За 1,000,000 елемента:

• Максимум: ~20 сравнения
• log₂(1,000,000) ≈ 19.9

⚠️Важно условие!

Критичното условие за двоично търсене е, че масивът трябва да бъде сортиран. Ако масивът не е сортиран, двоичното търсене няма да работи коректно!

4.2. Стъпка по Стъпка Логика

Алгоритъмът:

1. Инициализация: Дефинирайте low на началото (индекс 0) и high в края (индекс size - 1)
2. Условие за цикъл: Продължете докато low <= high
3. Изчисляване на средния индекс: mid = low + (high - low) / 2
4. Сравнение:
   • Ако arr[mid] == target → намерен! Върнете mid
   • Ако arr[mid] < target → търсете в дясната половина: low = mid + 1
   • Ако arr[mid] > target → търсете в лявата половина: high = mid - 1
5. Не е намерен: Ако цикълът завърши без намиране, върнете -1

ℹ️Визуализация на процеса

Масив: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Търсим: 13

Стъпка 1: low=0, high=9, mid=4 (arr[4]=11)  11 < 13 → дясно
Стъпка 2: low=5, high=9, mid=7 (arr[7]=19)  19 > 13 → ляво
Стъпка 3: low=5, high=6, mid=5 (arr[5]=13)  13 == 13 → намерен!

4.3. C++ Имплементация

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid; // Намерен
        } else if (arr[mid] < target) {
            low = mid + 1; // Търсим в дясната половина
        } else {
            high = mid - 1; // Търсим в лявата половина
        }
    }

    return -1; // Не е намерен
}

int main() {
    std::vector<int> data = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

    int target1 = 13;
    int result1 = binarySearch(data, target1);
    if (result1 != -1) {
        std::cout << "Елемент " << target1 << " намерен на индекс "
                  << result1 << std::endl;
    } else {
        std::cout << "Елемент " << target1 << " не е намерен." << std::endl;
    }

    int target2 = 10;
    int result2 = binarySearch(data, target2);
    if (result2 != -1) {
        std::cout << "Елемент " << target2 << " намерен на индекс "
                  << result2 << std::endl;
    } else {
        std::cout << "Елемент " << target2 << " не е намерен." << std::endl;
    }

    return 0;
}

✅Обяснение на ключови редове

• const std::vector<int>& arr: Константна препратка избягва скъпото копиране
• low + (high - low) / 2: По-безопасно от (low + high) / 2 (избягва overflow)
• while (low <= high): Продължаваме докато има валидно пространство за търсене
• return -1: Конвенция за "не е намерен"

4.4. Времева Сложност и Сравнителен Анализ

ℹ️Сложност

• Двоично Търсене: O(log n)
• Линейно Търсене: O(n)

Сравнение за различни размери:

Брой Елементи	Линейно (макс)	Двоично (макс)	Подобрение
100	100	7	14x
1,000	1,000	10	100x
1,000,000	1,000,000	20	50,000x
1,000,000,000	1,000,000,000	30	33,333,333x

✅Практически ситуации където двоичното търсене е критично

• Бази данни и индексиране: Бърз достъп до записи по ключ
• Търсачки: Намаляване на огромни сортирани списъци
• Системи в реално време: Финансови платформи, control системи
• Computational Geometry: Намиране на точки в диапазони

---

5. Практическа Демонстрация

5.1. Двоично Търсене със Стъпки

#include <iostream>
#include <vector>

int binarySearchWithSteps(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;

    std::cout << "--- Започваме двоично търсене за " << target << " ---\n";
    int step = 0;

    while (low <= high) {
        step++;
        int mid = low + (high - low) / 2;

        std::cout << "Стъпка " << step << ": ";
        std::cout << "Диапазон: [" << low << ", " << high << "], ";
        std::cout << "Среден индекс: " << mid << " (стойност: "
                  << arr[mid] << ")\n";

        if (arr[mid] == target) {
            std::cout << "Цел " << target << " намерена на индекс "
                      << mid << "!\n";
            return mid;
        } else if (arr[mid] < target) {
            std::cout << "  " << arr[mid] << " < " << target
                      << ". Търсим в дясната половина.\n";
            low = mid + 1;
        } else {
            std::cout << "  " << arr[mid] << " > " << target
                      << ". Търсим в лявата половина.\n";
            high = mid - 1;
        }
    }

    std::cout << "Цел " << target << " не е намерена след "
              << step << " стъпки.\n";
    return -1;
}

int main() {
    std::vector<int> data = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};

    std::cout << "Масив: [";
    for(int x : data) std::cout << x << " ";
    std::cout << "]\n\n";

    binarySearchWithSteps(data, 13);
    std::cout << "\n";
    binarySearchWithSteps(data, 6);

    return 0;
}

Масив: [1 3 5 7 9 11 13 15 17 19 ]

--- Започваме двоично търсене за 13 ---
Стъпка 1: Диапазон: [0, 9], Среден индекс: 4 (стойност: 9)
  9 < 13. Търсим в дясната половина.
Стъпка 2: Диапазон: [5, 9], Среден индекс: 7 (стойност: 15)
  15 > 13. Търсим в лявата половина.
Стъпка 3: Диапазон: [5, 6], Среден индекс: 5 (стойност: 11)
  11 < 13. Търсим в дясната половина.
Стъпка 4: Диапазон: [6, 6], Среден индекс: 6 (стойност: 13)
Цел 13 намерена на индекс 6!

--- Започваме двоично търсене за 6 ---
Стъпка 1: Диапазон: [0, 9], Среден индекс: 4 (стойност: 9)
  9 > 6. Търсим в лявата половина.
Стъпка 2: Диапазон: [0, 3], Среден индекс: 1 (стойност: 3)
  3 < 6. Търсим в дясната половина.
Стъпка 3: Диапазон: [2, 3], Среден индекс: 2 (стойност: 5)
  5 < 6. Търсим в дясната половина.
Стъпка 4: Диапазон: [3, 3], Среден индекс: 3 (стойност: 7)
  7 > 6. Търсим в лявата половина.
Цел 6 не е намерена след 4 стъпки.

---

6. Интерактивен Преглед и Дискусия

6.1. Предимства и Недостатъци на Масивите

✅ Предимства

• Константно време за достъп O(1)
• Ефективно използване на кеша
• Простота на имплементация
• Предсказуемо използване на памет
• Без memory overhead за указатели

⚠️ Недостатъци

• Фиксиран размер
• Скъпо вмъкване/изтриване O(n)
• Загуба на памет при предварително заделяне
• Изисква непрекъсната памет
• Не е гъвкав при променлив размер

6.2. Често Срещани Грешки при Двоично Търсене

⚠️Типични грешки

1. Грешно условие за цикъл: while (low < high) вместо while (low <= high)
2. Безкраен цикъл: low = mid или high = mid вместо mid + 1 / mid - 1
3. Integer overflow: (low + high) / 2 вместо low + (high - low) / 2
4. Неправилна инициализация: high = arr.size() вместо arr.size() - 1

❌

❌ Бъгнат код

int buggySearch(const vector<int>& arr, int target) {
  int low = 0;
  int high = arr.size(); // Грешка 1
  while (low < high) {   // Грешка 2
      int mid = (low + high) / 2; // Грешка 3
      if (arr[mid] == target) return mid;
      if (arr[mid] < target) low = mid;    // Грешка 4
      else high = mid;                      // Грешка 5
  }
  return -1;
}

✅

✅ Коректен код

int correctSearch(const vector<int>& arr, int target) {
  int low = 0;
  int high = arr.size() - 1; // Корекция 1
  while (low <= high) {       // Корекция 2
      int mid = low + (high - low) / 2; // Корекция 3
      if (arr[mid] == target) return mid;
      if (arr[mid] < target) low = mid + 1;  // Корекция 4
      else high = mid - 1;                    // Корекция 5
  }
  return -1;
}

6.3. Кога ДА НЕ използваме Двоично Търсене?

⚠️Неподходящи ситуации

Двоичното търсене НЕ е подходящо, когато:

• Данните не са сортирани (или сортирането е скъпо)
• Данните се променят често (вмъкване/изтриване е O(n) в масиви)
• Структурата не е масив (свързан списък няма O(1) достъп)
• Наборът от данни е много малък (overhead на binary search > простота на linear)

ℹ️Алтернативи

• Несортирани данни: Използвайте линейно търсене или hash таблици
• Често променящи се данни: Балансирани дървета (AVL, Red-Black)
• Свързани списъци: Линейно търсене или skip list
• Малки данни: Линейното търсене може да е по-бързо заради простотата

---

7. Заключение и Ключови Моменти

✅Какво научихме

Свойства на Масивите

• Масивите са линейни структури с непрекъснато разпределение на паметта
• Предоставят константен достъп O(1) до всеки елемент чрез индекс
• Характеризират се с фиксиран размер и хомогенни елементи
• Непрекъснатото съхранение осигурява cache locality

Обектно-Ориентиран Дизайн

• Инкапсулацията на масиви в класове позволява абстракция и модулност
• Custom Array класът предоставя безопасен интерфейс с проверка на границите
• Правилното управление на паметта (конструктор, деструктор, copy) е критично
• Този подход прави кода по-робустен и преизползваем

Двоично Търсене

• Изключителна ефективност: O(log n) времева сложност
• Предсказуема производителност: Бързо търсене дори в огромни данни
• Простота: Елегантна divide-and-conquer стратегия

Ограничения

• Изискване за сортирани данни: Масивът трябва да е сортиран
• Скъпи модификации: Вмъкване/изтриване е O(n)
• Фиксиран размер: По-малко гъвкавост от динамични структури

ℹ️Кратки препоръки за практика

1. Използвайте масиви за статични или рядко променящи се данни
2. Двоичното търсене е идеално за големи, сортирани колекции
3. За динамични данни разгледайте std::vector, hash таблици или дървета
4. Винаги проверявайте границите при работа с масиви
5. Практикувайте имплементирането на структури от данни за по-добро разбиране

---

Допълнителни Ресурси

Binary Search Туториали

• Binary Search - GeeksforGeeks - Изчерпателен туториал с приложения
• Binary Search Algorithm - TutorialsPoint - Базов алгоритъм и имплементация
• Binary Search with Python - W3Schools - Интерактивни примери
• Binary Search Tutorial - HackerEarth - С практически задачи

Визуализация и Примери

• Binary Search Visualization - Стъпка по стъпка анимация
• Binary Search - CS50 Harvard - Академичен материал
• Binary Search (With Code) - Programiz - C++, Java, Python примери

Arrays и Memory Layout

• Arrays in C++ - GeeksforGeeks - Основи на масиви в C++
• Understanding Array Memory Layout - Stack Overflow дискусии

Практически Задачи

• Binary Search Problems - LeetCode - Задачи за практика
• How to do Binary Search Step by Step - Пошагово ръководство
• Binary Search Algorithm - Intellipaat - Примери и задачи

Книги

• "Introduction to Algorithms" (CLRS) - Глава за Binary Search
• "The Algorithm Design Manual" by Steven Skiena - Searching Algorithms

---

Благодаря за вниманието! Успех с упражненията! 🎓