Operations on Array
There are many operations that can be performed on an array structure. Here we discuss the operations on array-like linear search, binary search, insertion, and deletion in an array, etc.
Topics Covered
Algorithms and C programs for the :
- Insertion in an array
- Deletion in an array
- Linear Search in an array
- Binary Search in an array
1. Insertion in an array
Time complexity for insertion is order of n i.e. O(n)
Algorithm for insertion in 1d array :
Algorithm insert array()
{
Steps:
1. Set I = N [Initialize counter]
2. Repeat While (I >= location)
3. Set A[I+1] = A[I] [Move elements downward]
4. Set I = I – 1 [Decrease counter by 1]
[End of While Loop]
5. Set A[location] = ITEM [Insert element]
6. Set N = N + 1 [Reset N]
7. Exit or Return
}
C program to implement insertion in an array
#include <stdio.h>
#include <conio.h>
int main()
{
int n;
scanf ("%d",&n);
int arr[n];
for( int i = 0; i < n; i++)
{
scanf("%d",&arr[i]);
}
int position;
scanf("%d",&position);
int element;
scanf("%d",&element);
if(position > n)
{
printf("Invalid Input");
}
else
{
for (int i = n - 1; i >= position - 1; i--)
{
arr[i+1] = arr[i];
arr[position-1] = element;
}
printf("Final array after insertion is:\n");
for (int i = 0; i <= n; i++)
{
printf("%d\n", arr[i]);
}
}
return 0;
}2. Deletion in an array
Time complexity for deletion is order of n i.e. O(n)
Algorithm for deletion in 1d array :
Algorithm deletearray()
{
Steps:
1. Set ITEM = A[location] [Assign the element to be deleted to ITEM]
2. Repeat For I = location to N
3. Set A[I] = A[I+1] [Move the Ith element upwards]
[End of For Loop]
4. Set N = N – 1 [Reset N]
5. Exit or Return
}C program to implement deletion in an array
#include <stdio.h>
#include <conio.h>
int main()
{
int array[100], position, c, n;
printf("Enter the number of elements of the array : ");
scanf("%d", &n);
printf("\nEnter the elements in the array : ");
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("\nEnter the position : ");
scanf("%d", &position);
if (position >= n+1)
printf("\nDeletion not possible.\n");
else
{
for (c = position - 1; c < n - 1; c++)
array[c] = array[c+1];
printf("\nFinal Array after deletion :");
for (c = 0; c < n - 1; c++)
printf("%d\n", array[c]);
}
return 0;
}3. Linear search in an array
Time complexity for linear search is order of n i.e. O(n)
Algorithm for linear search in 1d array :
function searchValue(value, target)
{
for (var i = 0; i < value.length; i++)
{
if (value[i] == target)
{
return i;
}
}
return -1;
}C program to implement linear search in an array
#include <stdio.h>
#include <conio.h>
void main()
{ int num;
int i, keynumber, found = 0;
printf("Enter the number of elements ");
scanf("%d", &number);
int array[num];
printf("Enter the elements one by one \n");
for (i = 0; i < number; i++)
{
scanf("%d", &array[i]);
}
printf("Enter the element to be searched ");
scanf("%d", &keynumber);
/* Linear search begins */
for (i = 0; i < number ; i++)
{
if (keynumber == array[i] )
{
found = 1;
break;
}
}
if (found == 1)
printf("Element is present in the array at position %d",i+1);
else
printf("Element is not present in the array\n");
}
4. Binary search in an array
Time complexity for binary search is order of nlogn i.e. O(nlogn)
Algorithm for binary search in 1d array :
Algorithm binarySearch()
{
Steps:
1. First=0;
2. Last=N-1;
3. Position=-1;
4. Flag=false;
5. While(First<=Last and Flag==false)
{
5.1 Middle=(first+last)div 2
If (Series[middle]==val)
{Position=middle;
Flag=true;
Break from the loop;
}
else
if (Series[middle]<Val) First=middle+1;
else Last=middle-1;
}
6. if(flag==true)
Prompt “The value found at the position ”:
Write Val;
else prompt “The value is not present in the array”;
}C program to implement binary search in an array
#include<stdio.h>
void main()
{
int arrb[100],i,n,x,f,l,m,flag=0;
printf("Input no. of elements in an array\n");
scanf("%d",&n);
printf("Input %d value in ascending order\n",n);
for(i=0;i<n;i++)
scanf("%d",&arrb[i]);
printf("Input the value to be search : ");
scanf("%d",&x);
/* Binary Search logic */
f=0;l=n-1;
while(f<=l)
{
m=(f+l)/2;
if(x==arrb[m])
{
flag=1;
break;
}
else if(x<arrb[m])
l=m-1;
else
f=m+1;
}
if(flag==0)
printf("%d value not found\n",x);
else
printf("%d value found at %d position\n",x,m);
}You can try these codes on your machine.
