Introduction to arrays

An array is a collection of items of same data type and size stored at contiguous memory locations and all elements are referred by a common name.Each array element is given a position number known as array index or subscript. An array index begins from 0 and the last index number is n-1.(n is the number of elements in array)

why are Arrays needed?

Assume we need to calculate the average height of all the students in a class. We have to declare 70 different variables to store the height values of all these students which is cumbersome. Even to write the expression for finding the average, we have to list down all these variables (al +a2+ . . +a65)/65. Furthermore, if the same program has to be extended for finding the average height of all students in the university, the declaration and manipulation of 1000's of variables become unmanageable.

Remember: “Location of next index depends on the data type we use”.

Defining an Array: Array definition are similar to defining any other variable. There are two things need to be kept in mind, data type of the array elements and the size of the array. The size of the array is fixed and the memory for an array needs to be allocated before use, size of an array cannot be increased or decreased dynamically.

Generally, arrays are declared as:

dataType arrayName[arraySize];

An array is distinguished from a normal variable 
by brackets [ and ].

Accessing array elements: Arrays allows to access elements randomly. Elements in an array can be accessed using indexes. Suppose an array named arr stores N elements. Indexes in an array are in the range of 0 to N-1, where the first element is present at 0-th index and consecutive elements are placed at consecutive indexes. Element present at ith index in the array arr[] can be accessed as arr[i].

for example:

2nd element=a[1]

3rd element=a[2]

nth element=a[n-1]

Advantages of using arrays:

*Arrays allow random access of elements. This makes accessing elements by position faster.

*Arrays have better cache locality that can make a pretty big difference in performance.

Examples:

// A character array in C/C++/Java

char arr1[] = {'a','k','j','h'};


// An Integer array in C/C++/Java

int arr2[] = {10, 20, 30, 40, 50};


// Item at i'th index in array is typically accessed

// as "arr[i]".  For example arr1[0] gives us 'a'

// and arr2[3] gives us 40.

                          Searching in an Array

Searching an element in an array means to check if a given element is present in an array or not. This can be done by accessing elements of the array one by one starting from the first element and checking if any of the element matches with the given element.

We can use loops to perform the above operation of array traversal and access the elements using indexes.

Suppose the array is named arr[] with size N and the element to be searched is referred as key. Below is the algorithm to perform to the search operation in the given array.

for(i = 0; i < N; i++)
{
    if(arr[i] == key)
    { 
        print "Element Found";
    }
    else
    {
        print "Element not Found";
    }
}

Time Complexity of this search operation will be O(N) in the worst case as we are checking every element of the array from 1st to last, so the number of operations is N.

Types of Arrays:

*One-dimensional array

*Two-dimensional array

*Multi-dimensional array\

1)one dimension arrays are already discussed in the above part.

example:

int a[5]={1,2,3,4,5};

float sample[3]= {3.0,9,12.5};

char c array[5]={'a', 'e' , 'i' , 'o', 'u'};

2) Two-dimensional arrays: This array can be defined as an array of several one-dimensional arrays. It can be visualized in the form of a table with rows and columns. It is an array with two indexes. One index represents the row number and the other the column number.

Syntax: data_type array_nainefrow_sizellcolunin_sizel ;

Example: int matrix[2][2];

Array initialization:  You can also initialize an array when you declare it (just like with variables).

int matrix[4][3]= { 34, 56, 67 }, { 12, 33, 23 }, { 14, 80, 85 }, { 13, 78, 90 };

int matrix[4][3] = { 34, 56, 67, 12, 33, 23, 14, 80, 85 , 13, 78, 90 } ;

int matrix[3][2] = {0};  // all elements are initialized to 0

int arr[2][ ] = { 12, 34, 23, 45, 56, 45 } ; //wrong (while initializing a 2-D array it is necessary to mention the second (column) dimension, whereas the first dimension (row) is optional) 

int arr[ ][ ] = ( 12, 34, 23, 45, 56, 45 ) ;  // wrong

Accessing Array elements: 

Each array element can be referred to by specifying its name followed by its row index number and column index number within square brackets. Matrix[0] [0] can be used to access the 0th row, 0th column element of the array.

matrix[2][1] represents an element in 2nd row and 1st column.

 

3) Multi-dimensional arrays: 

 A 2-D array can be defined as an array of several 1-D arrays. Likewise, a 3-D array can be defined as an array of several 2-D arrays. In general, an n-dimensional array can be defined as an array of several (n-1) dimensional arrays.

Example: sample[4][2][2] is a 3-D array with 4 two-D arrays. Each 2-D array has 2 rows and 2 columns.