Horje
Deleting Elements in an Array | Array Operations

In this post, we will look into deletion operation in an Array, i.e., how to delete an element from an Array, such as:

  1. Deleting Elements from an Array when it is Unsorted
  2. Deleting Elements from an Array when it is Sorted

Deleting Elements in an Array when it is Unsorted

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. 

C++

<?php
// PHP program to implement delete 
// operation in an unsorted array
 
// To search a key to be deleted
function findElement(&$arr, $n, $key)
{
    for ($i = 0; $i < $n; $i++)
        if ($arr[$i] == $key)
            return $i;
 
    return -1;
}
 
// Function to delete an element
function deleteElement(&$arr, $n, $key)
{
    // Find position of element to
    // be deleted
    $pos = findElement($arr, $n, $key);
 
    if ($pos == -1)
    {
        echo "Element not found";
        return $n;
    }
 
    // Deleting element
    for ($i = $pos; $i < $n - 1; $i++)
        $arr[$i] = $arr[$i + 1];
 
    return $n - 1;
}
 
// Driver code
$arr = array(10, 50, 30, 40, 20);
 
$n = count($arr);
$key = 30;
 
echo "Array before deletion\n";
for ($i = 0; $i < $n; $i++)
echo $arr[$i] . " ";
 
// Function call
$n = deleteElement($arr, $n, $key);
 
echo "\nArray after deletion\n";
for ($i = 0; $i < $n; $i++)
echo $arr[$i] . " ";
 
// This code is contributed by
// Rajput-Ji
?>

Output

Array before deletion
10 50 30 40 20 

Array after deletion
10 50 40 20

Time Complexity: O(N) 
Auxiliary Space: O(1)

Deleting Elements in an Array when it is Sorted

In the delete operation, the element to be deleted is searched using binary search, and then the delete operation is performed followed by shifting the elements.

Deleting 3 from the array

Performing delete operation

Below is the implementation of the above approach:

C++

// C++ program to implement delete operation in a
// sorted array
#include <bits/stdc++.h>
using namespace std;
 
// To search a key to be deleted
int binarySearch(int arr[], int low, int high, int key);
 
/* Function to delete an element */
int deleteElement(int arr[], int n, int key)
{
    // Find position of element to be deleted
    int pos = binarySearch(arr, 0, n - 1, 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;
}
 
int binarySearch(int arr[], int low, int high, int key)
{
    if (high < low)
        return -1;
    int mid = (low + high) / 2;
    if (key == arr[mid])
        return mid;
    if (key > arr[mid])
        return binarySearch(arr, (mid + 1), high, key);
    return binarySearch(arr, low, (mid - 1), key);
}
 
// Driver code
int main()
{
    int i;
    int arr[] = { 10, 20, 30, 40, 50 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 30;
 
    cout << "Array before deletion\n";
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
 
    // Function call
    n = deleteElement(arr, n, key);
 
    cout << "\n\nArray after deletion\n";
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
}
 
// This code is contributed by shubhamsingh10

C

// C program to implement delete operation in a
// sorted array
#include <stdio.h>
 
// To search a key to be deleted
int binarySearch(int arr[], int low, int high, int key);
 
/* Function to delete an element */
int deleteElement(int arr[], int n, int key)
{
    // Find position of element to be deleted
    int pos = binarySearch(arr, 0, n - 1, key);
 
    if (pos == -1) {
        printf("Element not found");
        return n;
    }
 
    // Deleting element
    int i;
    for (i = pos; i < n - 1; i++)
        arr[i] = arr[i + 1];
 
    return n - 1;
}
 
int binarySearch(int arr[], int low, int high, int key)
{
    if (high < low)
        return -1;
    int mid = (low + high) / 2;
    if (key == arr[mid])
        return mid;
    if (key > arr[mid])
        return binarySearch(arr, (mid + 1), high, key);
    return binarySearch(arr, low, (mid - 1), key);
}
 
// Driver code
int main()
{
    int i;
    int arr[] = { 10, 20, 30, 40, 50 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 30;
 
    printf("Array before deletion\n");
    for (i = 0; i < n; i++)
        printf("%d  ", arr[i]);
 
    // Function call
    n = deleteElement(arr, n, key);
 
    printf("\n\nArray after deletion\n");
    for (i = 0; i < n; i++)
        printf("%d  ", arr[i]);
}

Java

// Java program to delete an
// element from a sorted array
 
class Main {
 
    // Binary search
    static int binarySearch(int arr[], int low, int high,
                            int key)
    {
        if (high < low)
            return -1;
        int mid = (low + high) / 2;
        if (key == arr[mid])
            return mid;
        if (key > arr[mid])
            return binarySearch(arr, (mid + 1), high, key);
        return binarySearch(arr, low, (mid - 1), key);
    }
 
    /* Function to delete an element */
    static int deleteElement(int arr[], int n, int key)
    {
        // Find position of element to be deleted
        int pos = binarySearch(arr, 0, n - 1, key);
 
        if (pos == -1) {
            System.out.println("Element not found");
            return n;
        }
 
        // Deleting element
        int i;
        for (i = pos; i < n - 1; i++)
            arr[i] = arr[i + 1];
 
        return n - 1;
    }
 
    /* Driver Code */
    public static void main(String[] args)
    {
 
        int i;
        int arr[] = { 10, 20, 30, 40, 50 };
 
        int n = arr.length;
        int key = 30;
 
        System.out.print("Array before deletion:\n");
        for (i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
 
        // Function call
        n = deleteElement(arr, n, key);
 
        System.out.print("\n\nArray after deletion:\n");
        for (i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}

Python3

# Python program to implement delete operation in a
# sorted array
 
# /* Function to delete an element */
 
 
def deleteElement(arr, n, key):
 
    # Find position of element to be deleted
    pos = binarySearch(arr, 0, n - 1, key)
 
    if (pos == -1):
        print("Element not found")
        return n
 
    # Deleting element
    for i in range(pos, n - 1):
        arr[i] = arr[i + 1]
 
    return n - 1
 
# To search a key to be deleted
 
 
def binarySearch(arr, low, high, key):
 
    if (high < low):
        return -1
    mid = (low + high) // 2
 
    if (key == arr[mid]):
        return mid
    if (key > arr[mid]):
        return binarySearch(arr, (mid + 1), high, key)
 
    return binarySearch(arr, low, (mid - 1), key)
 
 
# Driver code
if __name__ == "__main__":
    arr = [10, 20, 30, 40, 50]
 
    n = len(arr)
    key = 30
 
    print("Array before deletion")
 
    for i in range(n):
        print(arr[i], end=" ")
 
    # Function call
    n = deleteElement(arr, n, key)
    print("\n\nArray after deletion")
    for i in range(n):
        print(arr[i], end=" ")
 
# This code is contributed by shubhamsingh10

C#

// C# program to delete an
// element from a sorted array
using System;
public class GFG {
 
    // Binary search
    static int binarySearch(int[] arr, int low, int high,
                            int key)
    {
        if (high < low)
            return -1;
        int mid = (low + high) / 2;
        if (key == arr[mid])
            return mid;
        if (key > arr[mid])
            return binarySearch(arr, (mid + 1), high, key);
        return binarySearch(arr, low, (mid - 1), key);
    }
 
    /* Function to delete an element */
    static int deleteElement(int[] arr, int n, int key)
    {
        // Find position of element to be deleted
        int pos = binarySearch(arr, 0, n - 1, key);
 
        if (pos == -1) {
            Console.WriteLine("Element not found");
            return n;
        }
 
        // Deleting element
        int i;
        for (i = pos; i < n - 1; i++)
            arr[i] = arr[i + 1];
 
        return n - 1;
    }
 
    /* Driver Code */
    public static void Main()
    {
 
        int i;
        int[] arr = { 10, 20, 30, 40, 50 };
 
        int n = arr.Length;
        int key = 30;
 
        Console.Write("Array before deletion:\n");
        for (i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
 
        // Function call
        n = deleteElement(arr, n, key);
 
        Console.Write("\n\nArray after deletion:\n");
        for (i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program to delete an
// element from a sorted array
 
    // binary search
    function binarySearch(arr,  low,  high,  key)
    {
        if (high < low)
            return -1;
        let mid = (low + high) / 2;
        if (key == arr[mid])
            return mid;
        if (key > arr[mid])
            return binarySearch(arr, (mid + 1), high, key);
        return binarySearch(arr, low, (mid - 1), key);
    }
 
    /* Function to delete an element */
    function deleteElement( arr,  n,  key)
    {
        // Find position of element to be deleted
        let pos = binarySearch(arr, 0, n - 1, key);
 
        if (pos == -1) {
            document.write("Element not found");
            return n;
        }
 
        // Deleting element
        let i;
        for (i = pos; i < n - 1; i++)
            arr[i] = arr[i + 1];
 
        return n - 1;
    }
 
    /* Driver Code */
     
        let i;
        let arr = [ 10, 20, 30, 40, 50 ];
 
        let n = arr.length;
        let key = 30;
 
        document.write("Array before deletion:\n");
        for (i = 0; i < n; i++)
            document.write(arr[i] + " ");
 
        n = deleteElement(arr, n, key);
 
        document.write("<br>"+"Array after deletion:\n");
        for (i = 0; i < n; i++)
            document.write(arr[i] + " ");
 // this code is contributed by shivanisinghss2110
 
</script>

Output

Array before deletion
10 20 30 40 50 

Array after deletion
10 20 40 50

Time Complexity: O(N). In the worst case all elements may have to be moved
Auxiliary Space: O(log N). An implicit stack will be used


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Types of Arrays Types of Arrays
Why Array Data Structures is needed? Why Array Data Structures is needed?
Array Representation in Data Structures Array Representation in Data Structures
Maximum illumination duration with reducing candles Maximum illumination duration with reducing candles
Construction of multiple AP Arrays Construction of multiple AP Arrays

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje