What is an Array?
An array is a collection of items of the same variable type that are stored at contiguous
memory locations. It’s one of the most popular and simple data structures and is often used
to implement other data structures. Each item in an array is indexed starting with 0.
We can directly access an array element by using its index value.
Basic terminologies of array
Array Index: In an array, elements are identified by their indexes. Array index starts
from 0.
Array element: Elements are items stored in an array and can be accessed by their
index.
Array Length: The length of an array is determined by the number of elements it can
contain.
Representation of Array
The representation of an array can be defined by its declaration. A declaration means
allocating memory for an array of a given size.
Array
int arr[5]; // This array will store integer type element
char arr[10]; // This array will store char type element
float arr[20]; // This array will store float type element
Array declaration
However, the above declaration is static or compile-time memory allocation, which means
that the array element’s memory is allocated when a program is compiled. Here only a fixed
size (i,e. the size that is mentioned in square brackets []) of memory will be allocated for
storage, but don’t you think it will not be the same situation as we know the size of the array
every time, there might be a case where we don’t know the size of the array. If we declare a
larger size and store a lesser number of elements will result in a wastage of memory or either
be a case where we declare a lesser size then we won’t get enough memory to store the rest of
the elements. In such cases, static memory allocation is not preferred.
Is it possible to create dynamic array?
The answer is Yes. It is possible to allocate memory dynamically. So, dynamic memory
allocation is the process of assigning the memory space during the execution time or the run
time.
int *array = new int[5];
Why Array Data Structures is needed?
Assume there is a class of five students and if we have to keep records of their marks in
examination then, we can do this by declaring five variables individual and keeping track of
records but what if the number of students becomes very large, it would be challenging to
manipulate and maintain the data.
What it means is that, we can use normal variables (v1, v2, v3, ..) when we have a small
number of objects. But if we want to store a large number of instances, it becomes difficult to
manage them with normal variables. The idea of an array is to represent many instances
in one variable..
Need for Array
Types of arrays:
There are majorly two types of arrays:
One-dimensional array (1-D arrays): You can imagine a 1d array as a row, where
elements are stored one after another.
1D array
Two-dimensional array: 2-D Multidimensional arrays can be considered as an array
of arrays or as a matrix consisting of rows and columns.
2D array
Three-dimensional array: A 3-D Multidimensional array contains three dimensions,
so it can be considered an array of two-dimensional arrays.
3D array
Types of Array operations:
Traversal: Traverse through the elements of an array.
Insertion: Inserting a new element in an array.
Deletion: Deleting element from the array.
Searching: Search for an element in the array.
Sorting: Maintaining the order of elements in the array.
Advantages of using Arrays:
Arrays allow random access to elements. This makes accessing elements by position
faster.
Arrays have better cache locality which makes a pretty big difference in performance.
Arrays represent multiple data items of the same type using a single name.
Arrays store multiple data of similar types with the same name.
Array data structures are used to implement the other data structures like linked lists,
stacks, queues, trees, graphs, etc.
Disadvantages of Array:
As arrays have a fixed size, once the memory is allocated to them, it cannot be
increased or decreased, making it impossible to store extra data if required. An array
of fixed size is referred to as a static array.
Allocating less memory than required to an array leads to loss of data.
An array is homogeneous in nature so, a single array cannot store values of different
data types.
Arrays store data in contiguous memory locations, which makes deletion and insertion
very difficult to implement. This problem is overcome by implementing linked lists,
which allow elements to be accessed sequentially.
Application of Array:
They are used in the implementation of other data structures such as array lists, heaps,
hash tables, vectors, and matrices.
Database records are usually implemented as arrays.
It is used in lookup tables by computer.
It is used for different sorting algorithms such as bubble sort insertion sort, merge
sort, and quick sort.
LINEAR SEARCH
Assume that item is in an array in random order and we have to find an item. Then the only
way to search for a target item is, to begin with, the first position and compare it to the target.
If the item is at the same, we will return the position of the current item. Otherwise, we will
move to the next position. If we arrive at the last position of an array and still can not find the
target, we return -1. This is called the Linear search or Sequential search.
Below is the code syntax for the linear search.
// Linear Search in C++
#include <iostream>
using namespace std;
int search(int array[], int n, int x)
{
// Going through array sequencially
for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}
BINARY SEARCH
In a binary search, however, cut down your search to half as soon as you find the middle of a
sorted list. The middle element is looked at to check if it is greater than or less than the value
to be searched. Accordingly, a search is done to either half of the given list
Below is the code syntax for the binary search.
#include <iostream>
using namespace std;
int binarySearch(int array[], int x, int low, int high)
{
// Repeat until the pointers low and high meet each
// other
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
Important Differences
Linear Search Binary Search
In binary search input data need to be in sorted
In linear search input data need not to be in sorted.
order.
It is also called sequential search. It is also called half-interval search.
The time complexity of linear search O(n). The time complexity of binary search O(log n).
Multidimensional array can be used. Only single dimensional array is used.
Linear search performs equality comparisons Binary search performs ordering comparisons
It is less complex. It is more complex.
It is very slow process. It is very fast process.
