Arrays

What is an Array?

An array is a collection of elements stored at contiguous memory locations. These elements are usually of the same data type, such as integers, floats, or strings.

Key Properties

• Fixed size (in most languages like C++, Java)

• Elements are indexed (starting from 0 in most languages)

• Provides random access using the index

---

Why Use Arrays?

• Efficiency: Constant-time access O(1) using an index

• Memory Management: Elements stored contiguously in memory

• Foundation for Other Data Structures: Arrays form the basis of lists, stacks, queues, heaps, etc.

---

Array Declaration & Initialization

In C++

int arr[5] = {1, 2, 3, 4, 5};

In Java

int[] arr = {1, 2, 3, 4, 5};

In Python

arr = [1, 2, 3, 4, 5]

---

Common Operations on Arrays

1. Traversal

Loop through elements using for or while.

 for i in range(len(arr)):
    print(arr[i])

Time Complexity: O(n)

---

2. Insertion

• At end: O(1) (if space available)

• At beginning or middle: O(n) (due to shifting elements)

---

3. Deletion

Similar to insertion:

• End: O(1)

• Anywhere else: O(n)

---

4. Searching

• Linear Search: O(n)

• Binary Search (on sorted arrays): O(log n)

// Binary Search Example
int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(arr[mid] == key) return mid;
        else if(arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

---

Advantages of Arrays

• Fast access using index

• Easy to implement

• Good for static data

Limitations

• Fixed size (cannot grow or shrink easily)

• Insertion and deletion can be costly

---

Applications of Arrays

• Storing multiple values of the same type

• Implementing matrices (2D arrays)

• Used in algorithms like sorting and searching

• Dynamic programming solutions rely on arrays