An array is a collection of items of same data type stored at contiguous memory locations.
This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array). The base value is index 0 and the difference between the two indexes is the offset.
let array = [4,3,8,1,0,14,6];
| Memory Location | Value |
|---|---|
| 1000 | 4 |
| 1001 | 3 |
| 1002 | 8 |
| 1003 | 1 |
| 1004 | 0 |
| 1005 | 14 |
| 1006 | 6 |
Accessing an element in an array is done by indexing into it.
array[0] // 4 (index 0 is the first element) (1000)
array[1] // 3 (index 1 is the second element) (1001)
array[2] // 8 (index 2 is the third element) (1002)
array[3] // 1 (index 3 is the fourth element) (1003)
array[4] // 0 (index 4 is the fifth element) (1004)
array[5] // 14 (index 5 is the sixth element) (1005)
array[6] // 6 (index 6 is the seventh element) (1006)
for initiation of Arrays it is necessary to specify size of an Array
if C++: for example if you wish to initate an array of 5 elements you have to write code as:
<datatype> arr_name[size]
int arr[5];
this will initialise array with 0 elements.
| Operation | Time Complexity |
|---|---|
| Accessing an element | O(1) |
| Searching an element | O(N) |
| Inserting an element | O(N) |
| Deleting an element | O(N) |
Algorithm :
-
Iterate the array using the loop.
-
Check whether the given key present in the array i.e. arr[i] == key.
-
If yes,
print "Element Found".
-
Else
print "Element Not Found".
Algorithm :
Binary_Search(a, lower_bound, upper_bound, val)
// 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search
Step 1: set beg = lower_bound, end = upper_bound, pos = - 1
Step 2: repeat steps 3 and 4 while beg <=end
Step 3: set mid = (beg + end)/2
Step 4: if a[mid] = val
set pos = mid
print pos
go to step 6
else if a[mid] > val
set end = mid - 1
else
set beg = mid + 1
[end of if]
[end of loop]
Step 5: if pos = -1
print "value is not present in the array"
[end of if]
Step 6: exit
It basically means inserting an element inside an array. There are following types of Insertions in Arrays
- Insertion at the beginning of an array
- Insertion at the given index of an array
- Insertion at the end of the Array
#include <stdio.h>
void main() {
int MAX=5;
int array[MAX] = {2, 3, 4, 5};
int N = 4; // number of elements in array
int i = 0; // loop variable
int value = 1; // new data element to be stored in array
// print array before insertion
printf("Printing array before insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d \n", i, array[i]);
}
// now shift rest of the elements downwards
for(i = N; i >= 0; i--) {
array[i+1] = array[i];
}
// add new element at first position
array[0] = value;
// increase N to reflect number of elements
N++;
// print to confirm
printf("Printing array after insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d\n", i, array[i]);
}
}
Output
Printing array before insertion −
array[0] = 2
array[1] = 3
array[2] = 4
array[3] = 5
Printing array after insertion −
array[0] = 0
array[1] = 2
array[2] = 3
array[3] = 4
array[4] = 5
#include<stdio.h>
int main()
{
int size=5;
int arr[size] = {1, 20, 5, 78, 30};
int element, pos, i;
printf("Enter position and element\n");
scanf("%d%d",&pos,&element);
if(pos <= size && pos >= 0)
{
//shift all the elements from the last index to pos by 1 position to right
for(i = size; i > pos; i--)
arr[i] = arr[i-1];
//insert element at the given position
arr[pos] = element;
/*
* print the new array
* the new array size will be size+1(actual size+new element)
* so, use i <= size in for loop
*/
for(i = 0; i <= size; i++)
printf("%d ", arr[i]);
}
else
printf("Invalid Position\n");
return 0;
}
Output
Enter position and element
5
5
1 20 5 78 30 5
#include <stdio.h>
void main()
{
int position, i, n, value,ch, arr[100];
printf("C Program to insert element at end of Array\n");
printf("First enter number of elements you want in Array\n");
scanf("%d", &n);
arr[n];
for(i = 0; i < n; i++)
{
printf("Please give value for index %d : ",i);
scanf("%d",&arr[i]);
}
printf("Let's Insert Element at end \n ");
printf("Please give a number to insert at end \n");
scanf("%d", &value);
arr[n] = value;
printf("Element %d is inserted at %d index \n",value,n);
printf("New Array is \n ");
for(i = 0; i < n+1; i++)
{
printf("%d \t",arr[i]);
}
}
Output
-
Deletion refers to removing an existing/given element from the array using indexes and re-organizing all elements of an array.
-
In the delete operation, the element to be deleted is searched using the linear search, and then the delete operation is performed followed by shifting the elements.
#include <iostream>
using namespace std;
// To search a key to be deleted
int findElement(int arr[], int n, int key);
// Function to delete an element
int deleteElement(int arr[], int n, int key)
{
// Find position of element to be deleted
int pos = findElement(arr, n, key);
if (pos == -1) {
cout << "Element not found";
return n;
}
// Deleting element
int i;
for (i = pos; i < n - 1; i++)
arr[i] = arr[i + 1];
return n - 1;
}
// Function to implement search operation
int findElement(int arr[], int n, int key)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == key)
return i;
return -1;
}
int main()
{
int i;
int arr[] = { 10, 50, 30, 40, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
cout << "Array before deletion\n";
for (i = 0; i < n; i++)
cout << arr[i] << " ";
n = deleteElement(arr, n, key);
cout << "Array after deletion"<<endl;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}