Module 2
Arrays
Array
• An array is a list of a finite number of homogenous (same type) data
elements such that:
• Elements of the array are referenced by an index set (n consecutive numbers)
• Array elements are stored in successive memory locations
• Array A of size n A[1..n]
• Array Attribute: n → Length or Size of the array ([Link])
• Size of (sub)array (Upper Index - Lower Index + 1) = (n-1+1) = n
• Array Indices 1 to n
• 𝑖 𝑡ℎ Element A[i]
Array Operations
• Traversal
• Insertion
• Deletion
• Search → Linear Search O(n) and Ω(1)
• Sorting
• Merging
Visualizing Arrays
A[1] A[2] A[3] A[4] A[5] A[6] A[1] 2
2 3 4 5 8 9
A[2] 3
A[3] 4
• Difference programming language → Different rules 5
A[4]
• Name of the array
8
• Data type of the array A[5]
• Index set of the array A[6]
9
Array Traversal
• Suppose we want to print the contents of an array
• Traversal (visiting)
TRAVERSAL(A, n) TRAVERSAL(A)
1 𝑖=1 1 for 𝑖 = 1 to n
2 while 𝑖 ≤ n 2 Print A[𝑖]
3 Print A[𝑖]
4 𝑖 =𝑖+1
• Time Complexity: Θ(𝑛) Space Complexity: Θ(1)
Insertion in an Array
• Insertion: Operation of adding another element to the array
• Insertion at the end: Example – Insert 99 at the end of an array
Index 1 2 3 4 5 6
22 33 44 55 66 77
• Array size = Array size + 1
Index 1 2 3 4 5 6 7
22 33 44 55 66 77 99
Insertion in an Array
• Insertion at the beginning: Example – Insert 99 at the beginning of an array
Index 1 2 3 4 5 6
22 33 44 55 66 77
• Array size = Array size + 1
Index 1 2 3 4 5 6 7
99 22 33 44 55 66 77
Insertion in an Array
• Insertion at the middle (anywhere else): Example – Insert 99 at index 𝑖 = 3
Index 1 2 3 4 5 6
22 33 44 55 66 77
• Array size = Array size + 1
Index 1 2 3 4 5 6 7
22 33 99 44 55 66 77
Array Insertion Algorithm
Insert an element x in array A of size n at index k
INSERT(A,n,k,x)
1 j = n
2 while j ≥ k
3 A[j+1] = A[j]
4 j=j–1
5 A[k] = x
6 n=n+1
• Time Complexity: O(n) and Ω(1)
Deletion in an Array
• Deletion: Operation of removing one element from the array
• Store the element in a variable for future use
• Deletion at the end: Example – Delete element at the last array index
Index 1 2 3 4 5 6
22 33 44 55 66 77
• Array size = Array size - 1
Index 1 2 3 4 5
22 33 44 55 66
Deletion in an Array
• Deletion at the beginning: Example – Insert element at first array index
Index 1 2 3 4 5 6
22 33 44 55 66 77
• Array size = Array size - 1
Index 1 2 3 4 5
33 44 55 66 77
Deletion in an Array
• Deletion at the middle (anywhere else): Example – Delete element at index
𝑖=3
Index 1 2 3 4 5 6
22 33 44 55 66 77
• Array size = Array size - 1
Index 1 2 3 4 5
22 33 55 66 77
Array Deletion Algorithm
Delete element at index k in array A of size n. Store
the value of deleted element in variable x
DELETE(A,n,k,x)
1 x = A[k]
2 while k ≤ n-1
3 A[k] = A[k+1]
4 k=k+1
5 n=n-1
• Time Complexity: O(n) and Ω(1)
Exercise
• Delete array element by value v
• Do a linear search for the value v
• Store the index 𝑖 at which v is found
• Delete element at index 𝑖
• Find the time complexity: O and Ω
Searching in an Array
• Linear Search: Find the location (index) of an item v in Array A of size n and store
the location in a variable loc
SEARCH(A, n, v, loc)
1 loc = 0
2 for i = 1 to n
3 if A[i] == v
4 loc = i
5 break
• Time Complexity: Ω(1) and O(n) Average Case Θ(𝑛)
• Binary Search: Sorted Array only
Binary Search
Binary Search: Find the location (index) of an item v in an sorted
Array A of size n and store the location in a variable loc
BINARY-SEARCH(A, n, v, loc)
1 loc = 0, start = 1, end = n
2 while start ≤ end
3 mid = (start + end)/2 Floor/Ceiling/Integer
4 if A[mid] == v
5 loc = mid
6 break
7 else if v<A[mid]
8 end = mid - 1
9 else // if v>A[mid]
10 start = mid + 1
Binary Search
• Time Complexity
Iteration No (Sub)Array Size When subarray reduces to single element, loop terminates
1 n/2 n/2𝑘 = 1
2 n/22 n = 2𝑘
3 n/23 k = log 2 𝑛
4 n/24
.. .. Time Complexity: Ω(1) and O(log 2 𝑛 )
k n/2𝑘
• Binary search in
• Dictionary
• Telephone directory
• IITR student list sorted by Enroll no