Data Structures and Algorithms

I
T
2
0 Arrays Data Structure
8
Lecture 2

1 Dr. Belal Murshed

 Data Structures and Algorithms

I
T
ARRAYS
2
0
8
Introduction

2 Dr. Belal Murshed

 Data Structures and Algorithms

Motivation
• You want to store 5 numbers in a program
I oNo problem. You define five int variables:
int num1, num2, num3, num4, num5;
T oEasy enough, right?
oBut what if you want to store 1000 numbers?
2 • Are you really going to make 1000 separate variables?
int num1, num2,..., num998, num999,
0 num1000;
• That would be CRAZY!
8 • So what is the solution?
oA data structure! Specifically, an array!
• An array is one of the most common data structures.

3 Dr. Belal Murshed

 Data Structures and Algorithms

Array
• An array is one of the most common data structures
I • An Array is a collection of elements of the same data
type, stored at a contiguous memory location.
T
• An array is a data structure that is used to store multiple
2 values of similar data types in a contiguous memory
locations under one name.
0
• An array’s elements are accessed by using their
8 positions in the structure.
• Declaration of array
Datatype ArrayName[size];
• Example
4 o int data]; Dr. Belal Murshed
 Data Structures and Algorithms

Basic Concepts
• Array name (data)
I
• Index/subscript (0...9)
T • The slots are numbered sequentially
2 starting at zero (Java, C++)
0 • If there are N slots in an array, the
8 index will be 0 through N-1
• Array length = N = 10
• Array size = N x Size of an element = 40
5 Dr. Belal Murshed
 Data Structures and Algorithms

Using Arrays
• Array_name[index]
I
• For example, in C++
T ocout<<data[4];
2 • will display 0
0
odata[3] = 99;
8 • Will replace -3 with 99

6 Dr. Belal Murshed

 Data Structures and Algorithms

Using Arrays
• data[ -1 ]  What will be the output of?
I oillegal  Data[8] = data[5] + 10
 data[3] = data[3] + 20
T • data[ 10 ]
oillegal (10 > upper bound)
2 • data[ 1.5 ]
oillegal
0
• data[ 0 ]
8 oOK
• data[ 9 ]
oOK
7 Dr. Belal Murshed
 Data Structures and Algorithms

Array Dimensionality
• One dimensional (just a linear list)
I
5 10 18 30 45 50 60 65 70 80
T oOnly one subscript is required to access an
2 individual element
0 • Two dimensional (matrix or table)
8 Col 0 Col 1 Col 2 Col 3
Row 0 20 25 60 40
Row 1 30 15 70 90
8 Dr. Belal Murshed
 Data Structures and Algorithms

2D Arrays
• Given the following array (whose name is
I ‘M’) 20 25 60 40
T 30 15 70 90
2 oTwo indices/subscripts are now required to
0 reference a given cell

8 • M[0][0] ?
• M[1][2] ?
• M[3][4] ?
9 Dr. Belal Murshed
 Data Structures and Algorithms

Representation of Array
• The representation of an array can be
I defined by its declaration.
T • A declaration means allocating memory for
2 an array of a given size.
0
8

10 Dr. Belal Murshed

 Data Structures and Algorithms

Array
Remember: “Location of next index depends on the data
type we use”.
I o For example, in the next Figure the data type in the array
is char, that means each character has only one byte then
T o We notice that the memory location of the first element
2 is 200,
o and the memory location of the next element is 201 .
0
8

11 Dr. Belal Murshed

 Data Structures and Algorithms

Array Declaration
• You declare an array as follows:
I Size=10;
int grades[Size];
T • This simply makes a an array variable (grades)
• array variable (grades) refers to an array of ten integers
2 • We can also declare the following:
int grades[10];
0 o Now the array variable grades refers to an array of ten integers
• By default, numeric elements are initialized to zero
8
Other example
int arr[5]; // This array will store integer type element
char arr[10]; // This array will store char type element
12 float arr[20]; // This array will store float type element
Dr. Belal Murshed
 Data Structures and Algorithms

Memory and Initialization

• When the array is created, memory is reserved
I for its contents
T • You can also specify the values for the array
instead of using the new operator
2
• Example:
0 int grade[] = {95, 93, 88}; //array of
3 ints
8
• To print the element at location number 1.
cout<< grade[1];

13 Dr. Belal Murshed

 Data Structures and Algorithms

Arrays’ Properties in C++

• An Array is a collection of data of the same
I data type, stored at a contiguous memory
T location.
2 • Indexing of an array starts from 0. ...
0 • Elements of an array can be accessed using
8 their indices.
• Once an array is declared its size remains
constant throughout the program.
14 Dr. Belal Murshed
 Data Structures and Algorithms

I
T
2 ARRAY
0
As a Data Structure
8

15 Dr. Belal Murshed

 Data Structures and Algorithms

What is an Array?
• An array is a data structure
I oAn array is a collection of items of same data type
stored at contiguous memory locations.
T oIt is a collection of multiple values of same type.
2 oExamples:
o An array of student grades
0 o An array of student names
o An array of objects (OOP perspective!)
8 • Assumption: Data in array is always sorted
• Array elements are initialized with “0”
16 Dr. Belal Murshed
 Data Structures and Algorithms

Array Characteristics
• Homogeneity
I oAll elements in an array must have the same data
type
T • Contiguous Memory
2 oArray elements (or their references) are stored in
contiguous/consecutive memory locations
0 • Direct access to an element
oIndex reference is used to access it directly
8
• Static data structure
oAn array cannot grow or shrink during program
execution…the size is fixed
17 Dr. Belal Murshed
 Data Structures and Algorithms

I
T
2 ARRAY
0
Operations
8

18 Dr. Belal Murshed

 Data Structures and Algorithms

Array Operations
1. Accessing/indexing an element using its index
I o Performance is very fast
o We can access an index immediately without searching
T o myArray [1250] = 55;
o we immediately access array spot 1250 of myArray
2 void access(double a[] , int index) {
0 a[index] = a[index] + a[index] * 0.20;
8 Cout<<“Updated value “<< a[index]);
}

19 Dr. Belal Murshed

 Data Structures and Algorithms

Array Operations
2. Traversing an array
I oDisplay all contents of an array
T • All elements will be displayed
• Every elements will be displayed exactly once
2
0 void display(int a[], int length)
{
8
for (int i=0; i<length; i++)

cout<<a[i]);
}
20 Dr. Belal Murshed
 Data Structures and Algorithms

Array Operations
3. Insertion: add an element at a certain
I index
T oWhat if we want to add an element at the
2 beginning?
• What if we add an element at the end?
0 o It would be FAST. Why? No need to shift.
• This would be a very slow operation! Why?
8 o Because we would have to shift ALL other elements over
one position

21 Dr. Belal Murshed

 Data Structures and Algorithms

Array Operations
(a) Insert operation in an unsorted array at the
I end :
T • In an unsorted array, the insert operation is
faster as compared to a sorted array because
2 we don’t have to care about the position at
which the element is to be placed.
0
8

22 Dr. Belal Murshed

 Data Structures and Algorithms

Insert operation in an unsorted

array at the end :
I
int insertSorted(int a[ ], int length, int value,
T int capacity)
length
{
2 // Cannot insert more elements if n is
// already more than or equal to capacity
0 if (length >= capacity)
return length;
8 arr[n] = key;
return (length + 1);
}

23 Time Complexity: O(1) Dr. Belal Murshed

 Data Structures and Algorithms

Insert operation in an unsorted array at the

end :
int main()
{
I int a[20] = { 12, 16, 20, 40, 50, 70 };
int capacity = sizeof(a) / sizeof(a[0]);
T int length = 6;
int i, value= 26;
2
cout << "Before Insertion: ";
0 for (i = 0; i < length ; i++)
cout << a[i] << " ";
8 // Inserting value
length = insertSorted(arr, length , value, capacity);
cout << "\nAfter Insertion: ";
for (i = 0; i < length ; i++)
cout << a[i] << " ";
return 0;
24 Dr. Belal Murshed
}
 Data Structures and Algorithms

Array Operations
(b) Insert an element at any position
I • Insert operation in an array at any position
can be performed by shifting elements to
T the right, which are on the right side of the
2 required position
0
8

25 Dr. Belal Murshed

 Data Structures and Algorithms

Insert an element at any position:

I
void insertElement(int a[], int length, int value,
T int pos)
length
{
2 // shift elements to the right
// which are on the right side of pos
0 for (int i = length - 1; i >= pos; i--)
a[i + 1] = a[i];
8 a[pos] = value;
}

Time complexity: O(N)

26 Dr. Belal Murshed
 Data Structures and Algorithms

Insert an element at any position:

int main()
{
int [15] = { 2, 4, 1, 8, 5 };
int length = 5;
I cout<<"Before insertion : ";
for (int i = 0; i < length ; i++)
T cout<<a[i]<<" ";
cout<<endl;
2 int value = 10, pos = 2;
// Function call
0 insertElement(a, length, value, pos);
length++;
8 cout<<"After insertion : ";
for (int i = 0; i < length; i++)
cout<<a[i]<<" ";
return 0;
}
27 Dr. Belal Murshed
 Data Structures and Algorithms

Array Operations
• Deletion: remove an element at a certain
I index
T oRemove an element at the beginning of the
2 array
• Performance is again very slow.
0 o Because ALL elements need to shift one position
backwards
8 oRemove an element at the end of an array
• Very fast because of no shifting needed

28 Dr. Belal Murshed

 Data Structures and Algorithms

Array Operations
(b) Delete Operation
I • In the delete operation, the element to be
deleted is searched using the (1)linear search,
T and then (2) the delete operation is performed
2 followed by(3) shifting the elements.
0
8

29 Dr. Belal Murshed

 Data Structures and Algorithms

Delete Operation:
int deleteElement(int a[], int length, int value)
{
// Find position of element to be deleted
I int pos = findElement(a, length, value);
if (pos == -1) {
T cout << "Element not found";
length
return length;
2 }

0 // Deleting element
int i;
8 for (i = pos; i < length - 1; i++)
a[i] = a[i + 1];
return length - 1;
}

Time complexity: O(N)

30 Dr. Belal Murshed
 Data Structures and Algorithms

Cont’s…… Delete
int findElement(int a[], int length, int value)
{
I for (int i=0; i<length; i++)
{
T if (a[i] == value)
{
return i;
2 }
}
0 return -1;
}
8
• The code returns location of the values
oIf found it will return Index of the value
oOtherwise it will return -1
31 Dr. Belal Murshed
 Data Structures and Algorithms

Cont’s ………..Delete Operation

int main()
{
int i;
int a[] = { 10, 50, 30, 40, 20 };
I int length = sizeof(a) / sizeof(arr[0]);
int value = 30;
T
cout << "Array before deletion\n";
2 for (i = 0; i < lemgth; i++)
cout << a[i] << " ";
0 // Function call
length = deleteElement(a, length, value);
8
cout << "\n\nArray after deletion\n";
for (i = 0; i < length; i++)
cout << a[i] << " ";
return 0;
32 } Dr. Belal Murshed
 Data Structures and Algorithms

Array Operations
• Merging: combining the data of two or
I more arrays into one
T oImplementation is left for student exercise
public static void merge(int[] a, int[] b) {
2
0
8

33 Dr. Belal Murshed

 Data Structures and Algorithms

Array Operations
• Searching through the array:
I • Depends on the algorithm
T • Some algorithms are faster than others
o More detail coming soon!
2 oLinear Search
0 oBinary Search
8

34 Dr. Belal Murshed

 Data Structures and Algorithms

I
T
2 Linear Search
0
8

35 Dr. Belal Murshed

 Data Structures and Algorithms

Linear Search
o In an unsorted array
I • The search operation can be performed by
linear traversal from the first element to
T the last element.
2
0
8

36 Dr. Belal Murshed

 Data Structures and Algorithms

Linear Search
bool search(int a[], int length, int value)
{
for (int i=0; i<length; i++)
I {
if (a[i] == value)
T {
return true;
2 }
}
0 return false;
}
8
• The code returns a Boolean value
oIf found it will return TRUE
oOtherwise FALSE
37 Dr. Belal Murshed
 Data Structures and Algorithms

Linear Search
int search(int a[], int length, int value)
{
I for (int i=0; i<length; i++)
{
T if (a[i] == value)
{
return i;
2 }
}
0 return -1;
}
8
• The code returns location of the values
oIf found it will return Index of the value
oOtherwise it will return -1
38 Dr. Belal Murshed
 Data Structures and Algorithms

I
T
2 Linear Search
0
Analysis
8

39 Dr. Belal Murshed

 Data Structures and Algorithms

Analysis of Linear Search

• Applicable for all data i.e. Sorted or Unsorted
I oBasic operation is “comparison”
T oThey ONLY way to be sure that a value isn’t in the
array is to look at every single spot of the array
2 oIf we have 100 elements then we have to make
0 100 comparisons to be sure about the value
oTherefore for “n” elements, the number of
8 comparisons will be “n” i.e. O(n)
oTime Complexity is O(n)

40 Dr. Belal Murshed

 Data Structures and Algorithms

I
T
2 Binary Search
0
8

41 Dr. Belal Murshed

 Data Structures and Algorithms

Binary Search (Introduction)

• Number Guessing Game from childhood
I oRemember the game you most likely played as
T a child
• I have a secret number between 1 and 100.
2
• Make a guess and I’ll tell you whether your guess is
0 too high or too low.
• Then you guess again. The process continues until
8 you guess the correct number.
• Your job is to MINIMIZE the number of guesses you
make.
42 Dr. Belal Murshed
 Data Structures and Algorithms

Binary Search (Introduction)

• Number Guessing Game from childhood
I oWhat is the first guess of most people?
• 50.
T oWhy?
• No matter the response (too high or too low), the most
2 number of possible values for your remaining search is
50 (either from 1-49 or 51-100)
0 • Any other first guess results in the risk that the possible
remaining values is greater than 50.
8 o Example: you guess 75
o I respond: too high
o So now you have to guess between 1 and 74
» 74 values to guess from instead of 50

43 Dr. Belal Murshed

 Data Structures and Algorithms

Binary Search (Introduction)

• Applicable only on Sorted array
I index 0 1 2 3 4 5 6 7 8
value 2 6 19 27 33 37 38 41 118
T
2 • We are searching for the value, 19
• So where is halfway between?
0 oOne guess would be to look at 2 and 118 and take
their average (60).
8 oBut 60 isn’t even in the list
oAnd if we look at the number closest to 60
• It is almost at the end of the array

44 Dr. Belal Murshed

 Data Structures and Algorithms

Binary Search (Introduction)

• We quickly realize that if we want to adapt the
I number guessing game strategy to searching
an array, we MUST search in the middle INDEX
T of the array.
2 index
value
0
2
1
6
2
19
3
27
4
33
5
37
6
38
7
41
8
118

0 • In this case:
8 oThe lowest index is 0
oThe highest index is 8
oSo the middle index is 4

45 Dr. Belal Murshed

 Data Structures and Algorithms

Binary Search (Introduction)

index 0 1 2 3 4 5 6 7 8
value 2 6 19 27 33 37 38 41 118
I
• We would ask, “is the number I am searching for, 19, greater or
T less than the number stored in index 4?
o Index 4 stores 33
2 • The answer would be “less than”
• So we would modify our search range to in between index 0
0 and index 3
o Note that index 4 is no longer in the search space
8 • We then continue this process
o The second index we’d look at is index 1, since (0+3)/2=1
o Then we’d finally get to index 2, since (2+3)/2 = 2
o And at index 2, we would find the value, 19, in the array
46 Dr. Belal Murshed
 Data Structures and Algorithms

Binary Search (Code return boolean)

bool binSearch(int a[], int length, int value) {
int low = 0;
I int high = length-1;
while (low <= high) {
T int mid = (low + high)/2;
if (value == a[mid])
2 return true; // meaning, “found”
else if (value < a[mid])
0 high = mid - 1;
else // if (value > a[mid]
8 low = mid + 1;
}
return false; // this only happens if not found

47 Dr. Belal Murshed

 Data Structures and Algorithms

Binary Search (Code return index)

int binSearch(int a[ ], int value) {
int low = 0;
I int high = length-1;
while (low <= high) {
T int mid = (low + high)/2;
if (value == a[mid])
2 return mid; // the index of value
else if (value < a[mid])
0 high = mid - 1;
else // if (value > a[mid]
8 low = mid + 1;
}
return -1; // this only happens if not found

48 Dr. Belal Murshed

 Data Structures and Algorithms

I
T
2 Binary Search
0
Analysis
8

49 Dr. Belal Murshed

 Data Structures and Algorithms

Analysis of Binary Search

• Let’s analyze how many comparisons (guesses) are
I necessary when running this algorithm on an array
of n items
T First, let’s try n = 128
o After 1 guess, we have 64 items left,
2 o After 2 guesses, we have 32 items left,
o After 3 guesses, we have 16 items left,
0 o After 4 guesses, we have 8 items left,
8 o After 5 guesses, we have 4 items left,
o After 6 guesses, we have 2 item left
o After 7 guesses, we have 1 items left.
o After 8 guesses, we have 0 items left.
50 Dr. Belal Murshed
 Data Structures and Algorithms

Analysis of Binary Search

• General case for n items
I oAfter 1 guesses, we have n/2 items left,
T oAfter 2 guesses, we have n/4 items left,
oAfter 3 guesses, we have n/8items left,
2 oAfter 4 guesses, we have n/16 items left,
0 o…………………
o…………………
8
o…………………
oSo on until we have 1 item left

51 Dr. Belal Murshed

 Data Structures and Algorithms

Analysis of Binary Search

• General case for n items
I oAfter 1 guesses, we have n/2 items left, n/21
T oAfter 2 guesses, we have n/4 items left, n/22
oAfter 3 guesses, we have n/8items left, n/23
2 oAfter 4 guesses, we have n/16 items left, n/24
0 o…………………
oAfter 10 guesses, we have n/210
8 n/2k
oAfter k guesses, we have
oWe will stop when we left with 1 item

52 Dr. Belal Murshed

 Data Structures and Algorithms

Analysis of Binary Search

• So we will stop once
I
n
T k
1 n2 k
k  log 2 n
2 2
0 • This means that a binary search
8 roughly takes log2n comparisons when
searching in a sorted array of n items
• Efficiency of Binary Search is O(log2n)
53 Dr. Belal Murshed
 Data Structures and Algorithms

Linear Search vs Binary Search

• Linear search O(n)
I
• Binary Search O(log2n)
T
• Binary Search is more efficient
2 n log n
0 8 3
1024 10
8 65536 16
1048576 20
33554432 25
1073741824 30

54 Dr. Belal Murshed

 Data Structures and Algorithms

I
T
List Matching
2 Problem
0
8

55 Dr. Belal Murshed

 Data Structures and Algorithms

List Matching Problem

• You are given two lists of Last Names
I oWithin each list, all names are distinct
T oAlso, each list is unsorted / sorted
2 • Problem:
0 oOutput the names common to both lists
8

56 Dr. Belal Murshed

 Data Structures and Algorithms

Sorted List Matching Problem

• Solution 01 (Brute Force – Unsorted lists)
I oFor each name on list #1, do the following:
T a) Search for the current name in list #2
b) If the name is found, output it.
2
0 oSteps a and b are run for each of the n names
8 in List #1, resulting in an O(n2) running time.

57 Dr. Belal Murshed

 Data Structures and Algorithms

Sorted List Matching Problem

• Solution 01 (Brute Force - Unsorted lists)
I void printMatches(string lst1[], string lst2[], int length1,
int length2)
T {
int i, j;
for (i = 0; i < length1; i++)
2 {
for (j = 0; j < length2; j++)
0 {
if (lst1[i].compare(lst2[j]) == 0)
8 cout<<(lst1[i])<<"
//break;
";

}
}
58 Dr. Belal Murshed
 Data Structures and Algorithms

Sorted List Matching Problem

• Solution 02 (One Sorted List)
I o Compare the target to the middle item in the list.
o If the target is the same as the middle item
T • you've found the target.
o If it's before the middle item
2 • repeat this procedure on the items before the middle.
o If it's after the middle item
0 • repeat on the items after the middle.
8 oThe method halves the number of items to check
each time. So It runs in logarithmic time: O(log n)
oMatching n items of list 1 will take O(n log n)

59 Dr. Belal Murshed

 Data Structures and Algorithms

Sorted List Matching Problem

• Solution 02 (One Sorted List)
I public static void printMatches(String lst1[], String lst2[],
int Length1)
T {

2 int i;

for (i=0; i < length1; i++) {

0
if (binSearch(lst2, lst1[i]))
8
cout<<(list1[i]);
}
}

60 Dr. Belal Murshed

 Data Structures and Algorithms

Binary Search function (Cont’s..)

bool binSearch(int a[], int length, int value) {
int low = 0;
I int high = length-1;
while (low <= high) {
T int mid = (low + high)/2;
if (value == a[mid])
2 return true; // meaning, “found”
else if (value < a[mid])
0 high = mid - 1;
else // if (value > a[mid]
8 low = mid + 1;
}
return false; // this only happens if not found

61 Dr. Belal Murshed

 Data Structures and Algorithms

Sorted List Matching Problem

• Solution 03 (Both Sorted Lists)
I 1) Start two “markers”
 One for each list, at the beginning of both lists
T 2) Repeat the following steps until one marker has
reached the end of the list
2 a) Compare the two names that the markers are pointing
at
0 b) If they are equal,
 Output the name and advance BOTH makers one spot
8 c) If they are NOT equal,
 Simply advance the marker pointing to the name that
comes earlier, alphabetically, one spot
• Try coding this up on your own
62 Dr. Belal Murshed
 Data Structures and Algorithms

Sorted List Matching Problem

• Solution 03 (Both Sorted Lists)
I List #1 List #2
T Adams Boston
Bell Davis
2 Davis Duncan
Harding Francis
0 Jenkins Gamble
8 Lincoln Harding
Simpson Mason
Zoeller Simpson

63 Dr. Belal Murshed

 Data Structures and Algorithms

Sorted List Matching Problem

• Solution 03 (Both Sorted Lists)
I oFor each loop iteration, we advance at least
T one marker
oAs such, the maximum number of iterations
2 would be the total number of names on both
lists, which is n, the length of both lists
0 • For each iteration, we are doing a constant amount
8 of work
• Essentially a comparison and/or outputting a name
oThus, this algorithm runs in about 2n steps i.e.
O(n)
64 Dr. Belal Murshed
 Data Structures and Algorithms

Array Operations
• Sorting: Arranging the values in ascending
I or descending order
T oInsertion Sort
2 oSelection Sort
oQuick Sort etc.
0
• This will be covered later on
8

65 Dr. Belal Murshed

 Data Structures and Algorithms

I
T
2
0
8

66 Dr. Belal Murshed