Array Insertion at Middle Index in DSA C++ - Execution Trace

Concept Flow - Array Insertion at Middle Index

Start with array

↓

Find middle index

↓

Shift elements right from middle

↓

Insert new element at middle

↓

Array updated with new element

The process finds the middle index, shifts elements right to make space, then inserts the new element there.

Execution Sample

DSA C++

int arr[6] = {1, 2, 4, 5, 6};
int n = 5;
int mid = n / 2;
int x = 3;
for (int i = n; i > mid; i--) arr[i] = arr[i-1];
arr[mid] = x; n++;

Inserts element 3 at the middle index of the array by shifting elements right.

Execution Table

Step	Operation	Index/Pointer	Array State	Pointer Changes	Visual State
1	Initial array	-	[1, 2, 4, 5, 6, _]	head=0, n=5	1 -> 2 -> 4 -> 5 -> 6 -> _
2	Calculate middle index	mid = 2	-	-	Index 2 selected for insertion
3	Shift element at index 4 to 5	i=5	[1, 2, 4, 5, 6, 6]	i moves from 5 to 4	1 -> 2 -> 4 -> 5 -> 6 -> 6
4	Shift element at index 3 to 4	i=4	[1, 2, 4, 5, 5, 6]	i moves from 4 to 3	1 -> 2 -> 4 -> 5 -> 5 -> 6
5	Shift element at index 2 to 3	i=3	[1, 2, 4, 4, 5, 6]	i moves from 3 to 2	1 -> 2 -> 4 -> 4 -> 5 -> 6
6	Insert new element 3 at index 2	arr[2] = 3	[1, 2, 3, 4, 5, 6]	n incremented to 6	1 -> 2 -> 3 -> 4 -> 5 -> 6
7	Final array	-	[1, 2, 3, 4, 5, 6]	n=6	1 -> 2 -> 3 -> 4 -> 5 -> 6

💡 All elements shifted right from middle, new element inserted, array size updated

Variable Tracker

Variable	Start	After Step 2	After Step 6	Final
arr	[1, 2, 4, 5, 6, _]	[1, 2, 4, 5, 6, _]	[1, 2, 3, 4, 5, 6]	[1, 2, 3, 4, 5, 6]
n	5	5	6	6
mid	-	2	2	2
i	-	undefined	2 (last shift)	-

Key Moments - 3 Insights

Why do we shift elements starting from the end and not from the middle forward?

Shifting from the end prevents overwriting elements before they are moved. See steps 3 to 5 in execution_table where elements move right starting from the last index.

Why is the middle index calculated as n/2 and not (n-1)/2?

Using n/2 gives the correct middle position for insertion in zero-based arrays. For n=5, mid=2 points to the third element, which is the middle. Refer to step 2 in execution_table.

What happens to the array size after insertion?

The size variable n is incremented by 1 after insertion to reflect the new element. See step 6 and 7 where n changes from 5 to 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the array state?

A [1, 2, 4, 4, 5, 6]

B [1, 2, 4, 5, 5, 6]

C [1, 2, 3, 4, 5, 6]

D [1, 2, 4, 5, 6, 6]

💡 Hint

Check the 'Array State' column at step 4 in execution_table

At which step does the new element get inserted into the array?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look for 'Insert new element' operation in execution_table

If the array size n was 6 instead of 5, what would be the middle index for insertion?

A 3

B 2

C 4

D 5

💡 Hint

Middle index is calculated as n/2, see variable_tracker for mid calculation

Concept Snapshot

Array Insertion at Middle Index:
- Find middle index as n/2
- Shift elements right from last to middle
- Insert new element at middle
- Increment array size n
- Shifting from end avoids overwriting
- Works for zero-based arrays

Full Transcript

This visual trace shows how to insert an element in the middle of an array. First, we find the middle index by dividing the current size by two. Then, starting from the last element, we shift each element one position to the right until we reach the middle index. This creates space to insert the new element without losing data. After inserting the new element at the middle index, we increase the size of the array by one. The execution table tracks each step, showing how the array changes and how pointers move. Key moments clarify why shifting starts from the end and how the middle index is chosen. The quiz tests understanding of array states and index calculation. This method keeps the array ordered and correctly sized after insertion.

Practice

1. What does inserting an element at the middle index of an array mean?

easy

A. Adding a new element exactly in the center, shifting others right

B. Replacing the middle element with a new one

C. Adding a new element at the end of the array

D. Removing the middle element from the array

Solution

1. Step 1: Understand middle index insertion

   Inserting at the middle means placing a new element at the center position, pushing existing elements right.

2. Step 2: Differentiate from other operations

   Replacing or removing elements is not insertion; adding at the end is not middle insertion.

3. Final Answer:

   Adding a new element exactly in the center, shifting others right -> Option A

4. Quick Check:

   Middle insertion means insert and shift right [OK]

Hint: Middle insertion shifts elements right from center [OK]

Common Mistakes:

• Thinking insertion replaces the middle element
• Confusing insertion with appending at the end
• Assuming middle means removing element

2. Which of the following C++ code snippets correctly inserts an element `x` at the middle index of array `arr` of size `n`?

easy

A. arr[n] = x; for(int i = n/2; i < n; i++) arr[i] = arr[i+1];

B. for(int i = 0; i < n/2; i++) arr[i] = arr[i+1]; arr[n/2] = x;

C. arr[n/2] = x; for(int i = n/2; i < n; i++) arr[i+1] = arr[i];

D. for(int i = n; i > n/2; i--) arr[i] = arr[i-1]; arr[n/2] = x;

Solution

1. Step 1: Shift elements right from middle index

   Loop from end (n) down to middle (n/2 + 1) shifting elements right to make space.

2. Step 2: Insert element at middle index

   Assign new element x at index n/2 after shifting.

3. Final Answer:

   for(int i = n; i > n/2; i--) arr[i] = arr[i-1]; arr[n/2] = x; -> Option D

4. Quick Check:

   Shift right then insert at middle [OK]

Hint: Shift elements right from end to middle before insert [OK]

Common Mistakes:

• Shifting elements left instead of right
• Inserting before shifting elements
• Incorrect loop direction causing overwrite

3. What is the output array after inserting 99 at the middle index of arr = {10, 20, 30, 40, 50} using the correct insertion method?

medium

A. [10, 20, 30, 40, 99, 50]

B. [10, 20, 99, 30, 40, 50]

C. [10, 20, 30, 99, 40, 50]

D. [10, 20, 30, 40, 50, 99]

Solution

1. Step 1: Calculate middle index

   Array size n=5, middle index = n/2 = 2 (0-based indexing).

2. Step 2: Shift elements right and insert 99

   Shift elements from index 4 to 2 right by one position, then insert 99 at index 2.

3. Final Answer:

   [10, 20, 99, 30, 40, 50] -> Option B

4. Quick Check:

   Insert at index 2 shifts right [OK]

Hint: Middle index = size/2; shift right, then insert [OK]

Common Mistakes:

• Inserting at wrong index (like 3 or 4)
• Not shifting elements before insertion
• Appending at the end instead of middle

4. Identify the error in the following code snippet that inserts element `x` at the middle index of array `arr` of size `n`:

for(int i = n/2; i < n; i++) {
  arr[i+1] = arr[i];
}
arr[n/2] = x;

medium

A. Loop shifts elements left instead of right

B. Index out of bounds when accessing arr[i+1]

C. Loop direction causes overwriting elements

D. No error, code works correctly

Solution

1. Step 1: Analyze loop direction and effect

   The loop moves forward from middle to end, copying arr[i] to arr[i+1], overwriting elements before they are moved.

2. Step 2: Identify correct approach

   Elements must be shifted right starting from the end backward to avoid overwriting data.

3. Final Answer:

   Loop direction causes overwriting elements -> Option C

4. Quick Check:

   Shift right must go backward to avoid overwrite [OK]

Hint: Shift elements right backward from end to middle [OK]

Common Mistakes:

• Shifting elements forward causing data loss
• Ignoring array bounds when shifting
• Assuming forward loop works for shifting right

5. Given an array arr = {5, 10, 15, 20, 25, 30} of size 6, after inserting element 99 at the middle index, what will be the final array?

hard

A. [5, 10, 15, 99, 20, 25, 30]

B. [5, 10, 99, 15, 20, 25, 30]

C. [5, 10, 15, 20, 99, 25, 30]

D. [5, 10, 15, 20, 25, 30, 99]

Solution

1. Step 1: Calculate middle index for even-sized array

   Array size n=6, middle index = n/2 = 3 (0-based indexing).

2. Step 2: Shift elements right from index 5 to 3

   Shift elements at indices 5,4,3 one position right to make space at index 3.

3. Step 3: Insert 99 at middle index

   Place 99 at index 3 after shifting.

4. Final Answer:

   [5, 10, 15, 99, 20, 25, 30] -> Option A

5. Quick Check:

   Insert at index 3 shifts right [OK]

Hint: For even size, middle = size/2; shift right, then insert [OK]

Common Mistakes:

• Inserting at index 2 instead of 3
• Not shifting elements before insertion
• Appending at the end instead of middle