ARRAYS
Week 2
1
Data Structures
Data structure
A particular way of storing and organising data in a
computer so that it can be used efficiently
Types of data structures
Based on memory allocation
o Static (or fixed sized) data structures (Arrays)
o Dynamic data structures (Linked lists)
Based on representation
o Linear (Arrays/linked lists)
o Non-linear (Trees/graphs)
Array: motivation
You want to store 5 numbers in a computer
Define 5 variables, e.g. num1, num2, ..., num5
What, if you want to store 1000 numbers?
Defining 1000 variables is a pity!
Requires much programming effort
Any better solution?
Yes, some structured data type
o Array is one of the most common structured data types
o Saves a lot of programming effort (cf. 1000 variable
names)
What is an Array?
A collection of data elements in which
all elements are of the same data type, hence
homogeneous data
o An array of students’ marks
o An array of students’ names
o An array of objects (OOP perspective!)
elements (or their references) are stored at contiguous/
consecutive memory locations
Array is a static data structure
An array cannot grow or shrink during program execution
– its size is fixed
Basic concepts
Array name (data)
Index/subscript (0...9)
The slots are numbered sequentially starting at
zero (Java, C++)
If there are N slots in an array, the index will be 0
through N-1
Array length = N = 10
Array size = N x Size of an element = 40
Direct access to an element
Homogeneity
Index: 0 1 2 3 4 5 6 7 8 9
Value: 5 10 18 30 45 50 60 65 70 80
All elements in the array must have the same data type
Value: 0 1 2 3 4
Index: 5.5 10.2 18.5 45.6 60.5
Index: 0 1 2 3 4
Value: ‘A’ 10.2 55 ‘X’ 60.5 Not an array
Contiguous Memory
Array elements are stored at contiguous memory
locations
Index: 0 1 2 3 4 5 6 7 8 9
Value: 5 10 18 30 45 50 60 65 70 80
Index: 0 1 2 3 4 5 6 7 8 9
Value: 5 10 18 45 60 65 70 80
No empty segment in between values (3 & 5 are empty
– not allowed)
Declaring and Creating Arrays
Declaring and Creating arrays
◦ Arrays are objects that occupy memory
◦ Created dynamically with keyword new
int c[] = new int[ 12 ];
Equivalent to
int c[]; // declare array variable
c = new int[ 12 ]; // create array
We can create arrays of objects too
String b[] = new String[ 100 ];
Using Arrays
Array_name[index]
For example, in Java
System.out.println(data[4]) will display 0
data[3] = 99 will replace -3 with 99
Using Arrays
Array_name[index]
For example, in Java
System.out.println(data[4]) will display 0
data[3] = 99 will replace -3 with 99
Using Arrays
Using an array initializer
Use initializer list
Items enclosed in braces ({})
Items in list separated by commas
int n[] = { 10, 20, 30, 40, 50 };
Creates a five-element array
Index values of 0, 1, 2, 3, 4
Do not need keyword new
Using Arrays (Cont.)
To declare an array follow the type with (empty) []s
int[] grade; //or
int grade[]; //both declare an int array
In Java arrays are objects so must be created with the new
keyword
To create an array of ten integers:
int[] grade = new int[10];
Note that the array size has to be specified, although it can be
specified with a variable at run-time
Examples Using Arrays (Cont.)
• Calculating the value to store in each array
element
– creates a 10-element array and assigns to each element one
of the even integers from 2 to 20 (2, 4, 6, …, 20).
Examples Using Arrays (Cont.)
Examples Using Arrays (Cont.)
Output:
Examples Using Arrays (Cont.)
Summing the elements of an array
Array elements can represent a series of values
We can sum these values
17
2 Dec 2023 Computer Science Department
Some more concepts
data[ -1 ] always illegal
data[ 10 ] illegal (10 > upper bound)
data[ 1.5 ] always illegal
data[ 0 ] always OK
data[ 9 ] OK
Q. What will be the output of?
1. data[5] + 10
2. data[3] = data[3] + 10
Array’s Dimensionality
19
Arrays in Java are one-dimensional; we use a
single index to access each cell of an array.
Nevertheless, there is a way we can define two-
dimensional arrays in Java we can create a two-
dimensional array as an array of arrays.
2 Dec 2023 Computer Science Department
Array’s Dimensionality
20
That is, we can define a two-dimensional array to
be an array with each of its cells being another
array. Such a two—dimensional array is sometimes
also called a matrix. In Java, we declare a two—
dimensional array as follows:
int[][] Y = new int[8][10];
This statement creates a two-dimensional "array of
arrays," Y, which is 8 × 10, having 8 rows and 10
columns. That is, Y is an array of length 8 such that
each element of Y is an array of length 10 of
integers.
2 Dec 2023 Computer Science Department
Array’s Dimensionality
One dimensional (just a linear list)
e.g., 5 10 18 30 45 50 60 65 70 80
Only one subscript is required to access an individual
element
Two dimensional (matrix/table)
e.g., 2 x 4 matrix (2 rows, 4 columns)
Col 0 Col 1 Col 2 Col 3
Row 0 20 25 60 40
Row 1 30 15 70 90
Multidimensional arrays
22
Figure 3.7: Illustration of a two-dimensional
integer array, Y, which has 8 rows and 10 columns.
The value of Y[3][5] is 100 and the value of Y[6]
[2] is 632
2 Dec 2023 Computer Science Department
Multidimensional arrays (Cont.)
Column 0 Column 1 Column 2 Column 3
Row 0
a[ 0 ][ 0 ] a[ 0 ][ 1 ] a[ 0 ][ 2 ] a[ 0 ][ 3 ]
Row 1
a[ 1 ][ 0 ] a[ 1 ][ 1 ] a[ 1 ][ 2 ] a[ 1 ][ 3 ]
Row 2
a[ 2 ][ 0 ] a[ 2 ][ 1 ] a[ 2 ][ 2 ] a[ 2 ][ 3 ]
Column index
Row index
Array name
Multidimensional arrays
Multidimensional arrays
Tables with rows and columns
Two-dimensional array
Declaring two-dimensional array b[2][2]
int b[][] = { { 1, 2 }, { 3, 4 } };
1 and 2 initialize b[0][0] and b[0][1]
3 and 4 initialize b[1][0] and b[1][1]
int b[][] = { { 1, 2 }, { 3, 4, 5 } };
row 0 contains elements 1 and 2
row 1 contains elements 3, 4 and 5
Multidimensional arrays (Cont.)
Creating multidimensional arrays
Can be allocated dynamically
3-by-4array
int b[][];
b = new int[ 3 ][ 4 ];
Rows can have different number of columns
int b[][];
b = new int[ 2 ][ ]; // allocate rows
b[ 0 ] = new int[ 5 ]; // allocate row 0
b[ 1 ] = new int[ 3 ]; // allocate row 1
Multidimensional arrays (Cont.)
Multidimensional arrays (Cont.)
Searching Arrays: Linear Search and Binary Search
Searching
Finding elements in large amounts of data
Determine whether array contains value matching key value
Linear searching
Binary searching
Searching Arrays: Linear Search and Binary Search
(Cont.)
Linear search
Compare each array element with search key
If search key found, return element index
If search key not found, return –1 (invalid index)
Works best for small or unsorted arrays
Inefficient for larger arrays
Linear Search
Linear Search(Cont.)
Output:
Key 34 found at index: 6
Key 421 found at index: 2
Binary Search
Binary search
◦ Efficient for large, sorted arrays
◦ Eliminates half of the elements in search through each pass
Compare middle array element to search key
If the middle element equals to search key
Return array index
If the search key is less than the middle element
Repeat search on first half of array
If the search key is greater than the middle element
Repeat search on second half of array
Continue search until
The middle element equals search key (success)
Search contains one element not equal to key (failure)
Binary Search (Cont.)
Binary Search (Cont.)
Output:
Key 14's position: 6
Key 432's position: 4
Binary Search Example
Exercises
36
Multiple Choice questions:
1. Which of these is an incorrect array declaration?
a) int arr[] = new int[5]
b) int [] arr = new int[5]
c) int arr[] = new int[5]
d) int arr[] = int [5] new
2 Dec 2023 Computer Science Department
Exercises
37
What is the output of this program?
1. class array_output
2. {
3. public static void main(String args[])
4. {
5. int array_variable [] = new int[10];
6. for (int i = 0; i < 10; ++i)
7. {
8. array_variable[i] = i;
9. System.out.print(array_variable[i] + " ");
10. i++;
11. }
12. }
13. }
a) 0 2 4 6 8
b) 1 3 5 7 9
c) 0 1 2 3 4 5 6 7 8 9
d) 1 2 3 4 5 6 7 8 9 10
2 Dec 2023 Computer Science Department
Exercises
38
What is the output of this program?
1. class multidimention_array
2. {
3. public static void main(String args[])
4. {
5. int arr[][] = new int[3][];
6. arr[0] = new int[1];
7. arr[1] = new int[2];
8. arr[2] = new int[3];
9. int sum = 0;
10. for (int i = 0; i < 3; ++i)
11. for (int j = 0; j < i + 1; ++j)
12. arr[i][j] = j + 1;
13. for (int i = 0; i < 3; ++i)
14. for (int j = 0; j < i + 1; ++j)
15. sum + = arr[i][j];
16. System.out.print(sum);
17. }
18. }
a) 11 b) 10
c) 13 d) 14
2 Dec 2023 Computer Science Department
Exercises
39
What is the output of this program?
1. class array_output
2. {
3. public static void main(String args[])
4. {
5. char array_variable [] = new char[10];
6. for (int i = 0; i < 10; ++i)
7. {
8. array_variable[i] = 'i';
9. System.out.print(array_variable[i] + "");
10. }
11. }
12. }
a) 1 2 3 4 5 6 7 8 9 10
b) 0 1 2 3 4 5 6 7 8 9 10
c) i j k l m n o p q r
d) i i i i i i i i i i
2 Dec 2023 Computer Science Department
40
References
Chapter 3.1, Data Structures and Algorithms by M.
Goodrich, R. Tamassia, M. Goldwasser, 6th Edition .
