What is Array? Searching and Sorting in Array | Learn DSA-3
This story will cover Array Traversal, Insertion, Deletion, Searching (Linear search, Binary search), and Sorting.
Array:
Arrays are a linear data structure that collects elements of the same data type.
Array works on an index system, its index starts from (0) to (n-1), where n is the size of the array.
One dimensional array:
1d array represents a row, where elements are stored one after another.
In the image below, 10 elements are stored in an array starting from index (0) to index (9). Each element is allocated with a memory size of 4 bytes and has addressed in memory starting from 201
Two-dimensional array:
2d array represents a table, where elements are stored in each cell of a table.
In the image below, 12 elements can be stored in this 2d array, one element in each cell, starting from (a[0][0]) to (a[2][3]).
For example: value 25 is stored at Row-1 and Column-3 at position a[0][2].
Three-dimensional array:
An array list of data elements makes a 1d (one-dimensional) array.
An array of 1d arrays makes a 2d (two-dimensional) array.
Similarly, an array of 2d arrays makes a 3d (three-dimensional) array.
A 3-D array can be declared as follows:
// declares an 3-D integer array
int arr[2][3][4]This array can store a total of 2 X 3 X 4= 24 elements.
Operations that can be performed on Array:
- Traversal
- Insertion
- Deletion
- Searching
- Sorting
1. Traversing the Array:
Traversing is the process of visiting each element once in an array.
2. Insertion in an Array:
Insertion is the process of adding one more element to the array. Insertion of an element can be done:
- Insertion at the beginning
- Insertion at the end
- Insertion at any given index of an array.
Insert at the beginning:
Insert at the end:
Insert at any given index of an array (at a specific position):
3. Deletion of an element from an Array:
Deletion of an element is the process of removing the desired element from an array. Deletion of an element can be done:
- Deletion at the beginning
- Deletion at the end
- Deletion of any element
Deletion at the beginning:
Deletion at the end:
Deletion of any element or at any given index from an array:
3. Searching for an Element
Searching means finding an element in an array. There are two ways we can search:
- Linear search
- Binary search
Linear Search:
Linear Search also called as sequential or simple search, it is the most basic search algorithm. For example: if given data structure is an array, and we search for an element by looking all the elements, until we find the desired element.
Linear search implementation:
arr = [10, 20, 30, 40, 50, 60]
If we find an element ‘10’, the algorithm will work very fast.
But if we find an element ‘60‘, the algorithm needs to loop through all the array. To calculate the Big O value we always look at the worst-case scenario.
So the algorithm complexity (Time complexity) for a Linear search is O(n).
Binary Search:
Binary search algorithm works on a sorted array (or any other data structure). For searching an item binary search uses Divide and Conquer approach. Compared with linear search, binary search is much faster.
The time complexity of Binary search is O(log n), where linear search works in O(n) time complexity.
