CHAPTER 7
ARRAYS
An array is by far the most powerful data structure in a programming language. This is the reason why it is in-built in all the HLLs, old as well as modern. We may not find any useful program without using an array.
7.1 Arrays in Java
An array is nothing but a sequential collection of items. We are allowed to refer to any item with the help of an index.
An item can be any of the following:
- Any simple data type like
int,char, and so on. - A
string - An object of a given class
- An array itself
The great strength of an array is that any particular element can be accessed with the help of the index. Just like C/C++, Java uses zero-based indexing. It means that index of the first element is always zero. It is not possible to define an array of elements, indexed say 1 to 10 or –5 to +5.
Let us assume we have a class of 20 students. They have recently obtained test marks. Every student has scored marks, which is of type int. To store all 20 marks, we need an array capable of storing 20 integers. If an array Marks[ ] is used for this purpose, Marks[0], Marks[1], …, Marks[19] are the twenty elements (variables); each of type int is used to store the data.
Short Questions and Answers
Q. What is an array?
A. An array is sequential collection of similar items.
Q. What is the great strength of an array?
A. Any particular element can be accessed directly with the help of the index.
For simplicity, at this stage, let us assume that arrays consist of elements belonging to simple data types. An array has a dimension (size). If an array has dimension 10, it means it can store 10 items. Each element of an array is referred with an array name and index. We may specify its dimension implicitly or explicitly. Once specified, the dimension cannot be changed later in a program.
7.2 Creating an Array
The first step in creating an array is to declare it. Arrays can be declared as follows:
int [] marks ;
Here, the variable marks is declared as an array of integer.
Alternatively, we can also declare the array as
int marks[] ;
This also means the same.
After declaring, we have to create an array with operator new.
marks = new int [3];
The above statement creates the array. This statement also allocates memory to it.
Here, the array is created with dimension three. Please note that while declaring, we have not specified the dimension. At this stage all the elements are initialized to zero.
Just like the declaration of other variables, we can couple declaration and initialization. See the following statement:
int marks[] = { 3,4,5 };
Here, we are declaring an array with the name Marks. We are initializing array elements as 3, 4, and 5. We have not specified the array dimension ourselves. As we have initialized with 3 values, array dimension is fixed as three. We may call it as implicit specification.
Those using C/C++ should note that declaration syntax int a[5] is not allowed in Java.
Let us try a program with arrays.
Problem: Write a program to find the average of given array elements.
Solution: Finding an average is simplest of all tasks. First, we have to add all the elements and then divide the sum by the number of elements (see Program 7.1).
PROGRAM 7.1 Finding Average
// array21.java
class array21
{ public static void main(String args[])
{ float total=0, avg ;
int i ;
int Marks[];
Marks = new int[5] ;
System.out.println(“---array21.java---”);
Marks[0] = 36;
Marks[1] = 46;
Marks[2] = 56;
Marks[3] = 66;
Marks[4] = 76;
for(i=0;i<5;i++)
total = total + Marks[i];
avg = (float)( total / 5.0) ;
System.out.println(“Average Marks are “ + avg);
}
}
If you run this program, you will get the following output.
---array21.java---
Average Marks are 56.0
Note that (total/5.0) returns a double value. Hence, it has to be typecast to float.
7.3 Array Index Checking
Java checks array index during runtime. If a program tries to use index out of bound, a runtime error occurs. You can see this in action in Program 7.6 (array3.java). This is a very good feature for a programming language. Non-checking can introduce hard-to-diagnose bugs. A Java programmer is protected from such trouble.
Discussion
Does Java check index at the compile time? The answer is “no”. The possible reason is that arrays are used with constant index very few times. Only in such cases the checking of compile time is possible. Most of the time array index is in the form of expression. Value of this expression is not known at the time of compilation. Hence, index checking in such cases is not possible. See program array5a.java in Section 7.6.
The size of the array is specified by the programmers. But for some reason, we may want to know the size of an array. Java has attached a property length to arrays. If we say
array_name.length
it will represent the length of the array named array_name. For example, in the previous example, if we say
Marks.length
it will represent the value 5. Please note that length is not a method. Hence, no brackets are used with it.
7.4 Multi-Dimensional Arrays
Arrays in Java can have more than one dimension. Such arrays are termed as multi-dimensional arrays. Let us first study two-dimensional arrays. We are all familiar with N × N matrices. These can be stored using array with two dimensions. Let us start our study with a simple program for printing a matrix.
Problem: Write a program to print a matrix.
Solution: See Program 7.2.
PROGRAM 7.2 Printing a Matrix
// matrix1.java
// matrix reading and printing
class matrix1
{ public static void main(String arg[])
{ int i,j;
int matrix[][]={
{1,2,3},
{7,8,9}
};
System.out.println("<---matrix1.java starts--->");
for(i=0;i<=2;++i)
{ for(j=0;j<=2;++j)
System.out.print(" " + matrix[i][j]);
System.out.println();
}
}
}
If you run the program, you will get the following output.
Output
<---matrix1.java starts--->
1 2 3
4 5 6
7 8 9
Please note that we refer an element as matrix [i][j]. This syntax is same as that for C/C++. However, in mathematics, we write such an element as matrix [i, j]. In Java, we cannot write it in this form. We get compilation error.
7.4.1 Matrix addition
Matrix addition is a fairly simple task. The only condition is that both the matrices must be of the same size. Value of the resultant element is the sum of two corresponding elements.
Problem: Write a program to add two given matrices.
Solution: See Program 7.3.
PROGRAM 7.3 Matrix Addition
// matrixadd.java
//addition of two matrices
class matrixadd
{
public static void main(String arg[])
{ int i,j;
int matrix1[][]={ {1,2,3},
{4,5,6},
{7,8,9}
};
int matrix2[][]={ {11,12,13},
{24,25,26},
{37,38,39}
};
int matrix3[][]=new int[3][3];
System.out.println(“--->Program matrixadd.java starts<---”);
for(i=0;i<=2;++i)
for(j=0;j<=2;++j)
matrix3[i][j]=(matrix1[i][j] + matrix2[i][j]);
// printing
System.out.println(“Matrix1”);
for(i=0;i<=2;++i)
{ for(j=0;j<=2;++j)
System.out.print(“ ” + matrix1[i][j]);
System.out.println();
}
System.out.println(“Matrix2”);
for(i=0;i<=2;++i)
{ for(j=0;j<=2;++j)
System.out.print(“ ” + matrix2[i][j]);
System.out.println();
}
System.out.println(“Matrix3”);
for(i=0;i<=2;++i)
{ for(j=0;j<=2;++j)
System.out.print(“ ” + matrix3[i][j]);
System.out.println();
}
}
}
If you run the program, you will get the following output.
Output
--->Program matrixadd.java starts<---
7.4.2 Matrix multiplication
We can multiply two matrices if the number of columns of the first is same as the number of rows of the second. The (i, j)th element of the product is computed by adding the product of elements of the ith row of the first matrix with corresponding elements of the jth column of the second matrix.
C [i, j] = sum of all A [i, k] * B [k, j]
Problem: Write a program to multiply two given matrices.
Solution: See Program 7.4.
PROGRAM 7.4 Matrix Multiplication
// matrixmul1.java
//matrix multiplication
class matrixmul1
{ public static void main(String arg[])
{ int i,j,k,sum;
int matrix1[][]={ {1,0,0},
{0,1,0},
{0,0,1}
};
int matrix2[][]={ {1, 2, 3},
{14,15,16},
{27,28,29}
};
int matrix3[][]=new int [3][3];
System.out.println("<---matrixmul1.java--->");
// calculating
for(i=0;i<=2;i++)
for(j=0;j<=2;j++)
{ sum=0;
for(k=0;k<=2;k++)
sum+=matrix1[i][k] * matrix2[k][j];
matrix3[i][j]=sum;
}
System.out.println("matrix1");
for(i=0;i<=2;++i)
{ for(j=0;j<=2;++j)
System.out.print(" " + matrix1[i][j]);
System.out.println();
}
System.out.println("matrix2");
for(i=0;i<=2;++i)
{ for(j=0;j<=2;++j)
System.out.print(" " + matrix2[i][j]);
System.out.println();
}
System.out.println("matrix3");
for(i=0;i<=2;++i)
{ for(j=0;j<=2;++j)
System.out.print(" " + matrix3[i][j]);
System.out.println();
}
}
}
If you run the program, you will get the following output.
Output
<---matrixmul1.java--->
7.5 Enhanced for Loop
From version 5, Java decided to give additional power to for loop. Many times, we work with a collection of objects. We are required to work with each and every item of the collection. As this situation is very common, new syntax covers it very elegantly. As arrays are the simplest collection, let us see it first.
Consider an array of marks defined as
int Marks[ ]
Now we can set a loop as
for ( int j : Marks )
{ body of the loop }
Here, body of the loop is executed for every value j which is present in an array. We can say that this is equivalent to a standard for loop like
for ( i=0;i<Marks.length;i++)
{ body of the loop }
where, integer j in the first example represents Marks[i] of the second example.
Earlier we had seen a program to find the average (array21.java). Let us rewrite it using enhanced for loop.
Problem: Write a program to find the average of a given array element using enhanced for loop.
Solution: See Program 7.5.
PROGRAM 7.5 Enhanced for Loop
// array22.java
class array22
{ public static void main(String args[])
{ float total=0, avg ;
int i ;
int Marks[];
System.out.println("<---array22.java--->");
Marks[0] = 36;
Marks[1] = 46;
Marks[2] = 56;
Marks[3] = 66;
Marks[4] = 76;
for(int j : Marks)
total = total + j ;
avg = (float)( total / 5.0) ;
System.out.println("Average Marks are " + avg);
}
}
If you run the program, you will get the following output.
Output
<---array22.java--->
Average Marks are 56.0
If you consider this as a trivial example, let us discuss a very complex collection like HashSet. Here, we have to move from element to element only with the help of Iterator. In such a collection, we can use enhanced for loop very easily. We will discuss this example in Chapter 23.
7.6 End of Chapter Programs
7.6.1 Array index out of bound
Problem: Write a program to show that Java checks array index.
Solution: See Program 7.6.
PROGRAM 7.6 Java Checks Array Index Automatically
// array3.java
class array3
{ public static void main(String args[])
{ float x=0,y=0 ;
int i;
int A[];
A = new int[3] ;
System.out.println("<---array3.java--->");
A[0]=3;
A[1]=4;
A[2]=5;
A[3]=6;
for(i=0;i<4;i++)
System.out.println("Average of A is" + x/4.0);
}
}
If you run the program, you will get the following output.
Output
<---array3.java--->
Exception in thread "main"
java.lang.ArrayIndexOutOfBoundsException: 3
at array3.main(array3.java:12)
When an array index is out of bound, the program throws what is known as ArrayIndexOutOfBoundsException. We will study errors and exceptions in Chapter 19. At this stage, we will only say that exceptions are very useful in program development.
7.6.2 Binary search
Binary search is the fastest search technique. It requires data to be sorted. It finds the given number in much less efforts (log n) as compared to other searching techniques. The algorithm can be explained in brief as follows.
At any time, searching is confined to a range. To begin with, range is the entire array. First, we get the element at the middle of the range. We compare the search item with the value of this element.
If the value matches, we have successfully found the element.
If search element is smaller, new range is from start to middle.
If search element is larger, new range is middle to end.
When the search range reduces to one, we stop searching further. Let us try this algorithm.
Problem: Write a program to find a given number in a given array using binary search algorithm.
Solution: See Program 7.7.
PROGRAM 7.7 Binary Search
// search1.java
class search1
{ public static void main(String args[])
{ int i,l,r,n,k;
int[] a = {1,12,13,23,25,37,41,47,51,59};
boolean found;
n = 13; // number to find
System.out.println(“The input data is as follows”);
System.out.println(“1,12,13,23,25,37,41,47,51,59”);
System.out.println(“The number To be searched : ” + n );
found = false;
l=0;r=9; // array index in java is 0 to 9
do
{ k=(l+r)/2 ;
if (a[k]==n)
else { if (a[k]<n ) l=k+1;
else r=k-1;
}
} while ((!found)&&(l<=r));
if (found)
System.out.println (“The number is found”);
else
System.out.println (“The number is NOT found”);
return ;
}
}
If you run the program, you will get the following output.
Output
The input data is as follows
1,12,13,23,25,37,41,47,51,59
The number To be searched : 13
The number is found
7.6.3 Linear search
We have seen the fastest search just now. However, it requires that data must be sorted. What if the data is unsorted? Then we have to use a simple technique called linear search. It finds a given number simply by examining every array element one by one sequentially.
Problem: Write a program to find a given number in a given array using the linear search method.
Solution: See Program 7.8.
PROGRAM 7.8 Linear Search
// search2.java
// linear search
class search2
{ public static void main(String args[])
{ int i,n;
int[] a = {59,13,37,25,51,1,23,41,47,12};
boolean found;
n = 47; // number to find
System.out.println (“<---search2.java--->”);
System.out.println(“The input data is as follows”);
System.out.println(“59,13,37,25,51,1,23,41,47,12”);
System.out.println(“The number To be searched : “ + n );
found = false;
for(i=0;i<10;i++)
{ System.out.println(“checking “ + i +” th number = “+ a[i]);
if (a[i]==n)
{ found = true;
break;
} ;
if (found)
System.out.println (“The number is found”);
else
System.out.println (“The number is NOT found”);
return ;
}
}
If you run the program, you will get the following output.
Output
<---search2.java--->
The input data is as follows
59,13,37,25,51,1,23,41,47,12
The number To be searched : 47
checking 0 th number = 59
checking 1 th number = 13
checking 2 th number = 37
checking 3 th number = 25
checking 4 th number = 51
checking 5 th number = 1
checking 6 th number = 23
checking 7 th number = 41
checking 8 th number = 47
The number is found
If you see the code carefully, you will notice the use of the break statement in the for loop. It is possible to replace this use of for with break by a while loop. Some experts will give more marks for such coding.
7.6.4 Checking for duplicate
In many applications, it is required that the data does not have any duplicate entries. Let us try a simple algorithm for checking duplicates.
Problem: Write a program to check for duplicate entries in a given array.
Solution: The simplest solution will have the following steps. First, consider the first entry (a[0]) as num. Then using a for loop, check it with all the remaining entries in an array. Now repeat this for all elements except the last one.
PROGRAM 7.9 Checking for Duplicates
// dup1.java
// checks for duplicate
// linear search
class dup1
{ public static void main(String args[])
{ int i,j,num;
int[] a = {59,13,37,25,51,1,23,41,37,12};
boolean found;
System.out.println (“<---dup1.java--->”);
System.out.println(“The input data is as follows”);
System.out.println(“59,13,37,25,51,1,23,41,37,12”);
System.out.println(“checking for duplicates” );
found = false;
for(i=0; i<10-1; i++)
{ System.out.println(“checking for “ + a[i]);
num = a[i];
for(j=i+1;j<10;j++)
if (num==a[j])
{ found = true;
System.out.println (“The duplicate number found”);
}
} ;
return ;
}
}
If you run the program, you will get the following output.
Output
<---dup1.java--->
The input data is as follows
59,13,37,25,51,1,23,41,37,12
checking for duplicates
checking for 59
checking for 13
checking for 37
The duplicate number found
checking for 25
checking for 51
checking for 1
checking for 23
checking for 41
checking for 37
Well, checking is simple. Can you remove the duplicate entries?
Earlier we have said that referring an array element as matrix [a, b] produces compilation error. We know that it is safer and hence better to catch these errors at compilation time. In C/C++, such reference does not necessarily produce compilation error. The program gets compiled and also executed, albeit with surprising and of course incorrect results. At least in this respect we can say Java is better than C++. (C++ programmers will know that this happens because C++ supports the comma operator. Java does not support comma operator.)
Keywords
array, array index checking, ArrayIndexOutOfBoundsException, binary search, linear search, matrix addition, matrix multiplication, multi-dimensional arrays, two-dimensional arrays, zero-based indexing
RuleBook
| array index checking | Java checks array index during runtime. If program tries to use index out of bound, a runtime error occurs. |
| array size | When an array size (dimension) is specified, it cannot be changed later in the program. |
| arrays methods | Arrays are passed to methods by call-by-reference. |
C++ Corner
In C++ there is no in-built array index checking. It is the responsibility of a programmer. Index going out of bounds generates hard-to-detect errors in C++. In Java, memory to an array is allocated using operator new! In C++, you may allocate memory this way. Alternately, a simple declaration like int a[5] allocates memory to an array in C++.
Review Questions
- Describe two methods to declare an array.
- How do you get the size of an array?
- Is index checking supported in Java?
Exercises
- Write a function to find the largest number from a given integer array.
- Write a function
binSearch()to find a given number from a given sorted integer array. - Develop a method to count the number of vowels in a given array of characters.
- Assume that a 4-bit binary number is stored in an array of characters. Write a program to print its value in Hexadecimal format.
- An array of char of size 4 is supposed to contain a number in hexadecimal format. Write a method
validate()which checks the validity of the stored number. Hint: anything other than 0,…, 9 and A,…, F is invalid. - Write a program to find the determinant of N × N matrix.
- Write a program to subtract one N × N matrix from other.
- An array contains marks obtained by students in a class test. Assume the number of students to be 60. The marks are between 0 and 100. Write a program to plot a Histogram. (As we have not studied graphics as yet, develop only in text mode. For convenience of programming, you may draw the bars in horizontal direction.)
- Assume that different schemes offer compound interest at rate 3%, 4%, 6% and 7%. Prepare a table showing amount returned if an investor invests Rs. 1,000 for a period of 1, 2, 3, 4, and 5 years.
- Write a program to remove duplicates from a given array.
- Rewrite program search2.java such that we do not need
breakstatement. Hint: Usewhile. - State whether the following program will compile. If yes, describe the output. If no, give reasons.
********************************************// array5b.javaclass array5b{ public static void main(String args[]){ int k=5;int a[] ;System.out.println(“<---array5b--->”);a=new int[5];k= a[3];System.out.println(k);}}********************************************