Home » Operations on Array

AlgorithmsData structures

Operations on Array

Arpit Jain

May 11, 2021

0

SaveSavedRemoved 0

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.