Search, Insert, and Delete in an Sorted Array | Array Operations

Last Updated : 05 Jul, 2023

How to Search in a Sorted Array?

In a sorted array, the search operation can be performed by using binary search.

Below is the implementation of the above approach:

C++

// C++ program to implement binary search in sorted array 
#include <bits/stdc++.h> 
using namespace std; 
  
int binarySearch(int arr[], int low, int high, int key) 
{ 
    if (high < low) 
        return -1; 
    int mid = (low + high) / 2; /*low + (high - low)/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() 
{ 
    // Let us search 3 in below array 
    int arr[] = { 5, 6, 7, 8, 9, 10 }; 
    int n, key; 
  
    n = sizeof(arr) / sizeof(arr[0]); 
    key = 10; 
  
    // Function call 
    cout << "Index: " << binarySearch(arr, 0, n - 1, key) 
         << endl; 
    return 0; 
} 
  
// This code is contributed by NamrataSrivastava1

C

// C program to implement binary search in sorted array 
#include <stdio.h> 
  
int binarySearch(int arr[], int low, int high, int key) 
{ 
    if (high < low) 
        return -1; 
    int mid = (low + high) / 2; /*low + (high - low)/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() 
{ 
    // Let us search 3 in below array 
    int arr[] = { 5, 6, 7, 8, 9, 10 }; 
    int n, key; 
  
    n = sizeof(arr) / sizeof(arr[0]); 
    key = 10; 
  
    // Function call 
    printf("Index: %d\n", binarySearch(arr, 0, n - 1, key)); 
    return 0; 
}

Java

// Java program to implement binary 
// search in a sorted array 
  
class Main { 
    // function to implement 
    // binary search 
    static int binarySearch(int arr[], int low, int high, 
                            int key) 
    { 
        if (high < low) 
            return -1; 
  
        /*low + (high - low)/2;*/
        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*/
    public static void main(String[] args) 
    { 
        int arr[] = { 5, 6, 7, 8, 9, 10 }; 
        int n, key; 
        n = arr.length - 1; 
        key = 10; 
  
        // Function call 
        System.out.println("Index: "
                           + binarySearch(arr, 0, n, key)); 
    } 
}

Python3

# python 3  program to implement 
# binary search in sorted array 
  
  
def binarySearch(arr, low, high, key): 
  
    mid = (low + high)/2
  
    if (key == arr[int(mid)]): 
        return mid 
  
    if (key > arr[int(mid)]): 
        return binarySearch(arr, 
                            (mid + 1), high, key) 
  
    if (key < arr[int(mid)]): 
        return binarySearch(arr, low, (mid-1), key) 
  
    return 0
  
  
# Driver code 
if __name__ == "__main__": 
    # Let us search 3 in below array 
    arr = [5, 6, 7, 8, 9, 10] 
    n = len(arr) 
    key = 10
  
    # Function call 
    print("Index:", int(binarySearch(arr, 0, n-1, key))) 
  
# This code is contributed by 
# Smitha Dinesh Semwal 

C#

// C# program to implement binary 
// search in a sorted array 
  
using System; 
  
public class GFG { 
  
    // function to implement 
    // binary search 
    public 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); 
    } 
  
    /* Driver Code */
    public static void Main(string[] args) 
    { 
        int[] arr = new int[] { 5, 6, 7, 8, 9, 10 }; 
        int n, key; 
        n = arr.Length; 
        key = 10; 
  
        // Function call 
        Console.WriteLine( 
            "Index: " + binarySearch(arr, 0, n - 1, key)); 
    } 
} 
  
// This code is contributed by Shrikant13

PHP

<?php 
// PHP program to implement 
// binary search in sorted array 
  
function binarySearch($arr, $low,  
                      $high, $key)  
{ 
    if ($high < $low)  
    return -1; 
      
    $mid = (int)($low + $high) / 2; 
      
    if ($key == $arr[(int)$mid]) 
        return $mid; 
      
    if ($key > $arr[(int)$mid])  
        return binarySearch($arr, ($mid + 1),  
                            $high, $key); 
      
    return (binarySearch($arr, $low,  
                        ($mid -1), $key)); 
} 
  
// Driver Code 
  
// Let us search 3 in below array 
$arr = array(5, 6, 7, 8, 9, 10); 
$n = count($arr); 
$key = 10; 
  
// Function call 
echo "Index: ", (int)binarySearch($arr, 0,  
                                  $n-1, $key); 
  
// This code is contributed by 
// Srathore 
?>

Javascript

<script> 
  
  
// Javascript program to implement  
// binary search in sorted array 
  
function binarySearch( arr, low, high, key) 
{ 
    if (high < low) 
        return -1; 
        /*low + (high - low)/2;*/
    let mid = Math.trunc((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 program 
      
    // Let us search 3 in below array 
    let arr = [ 5, 6, 7, 8, 9, 10 ]; 
    let n, key; 
  
    n = arr.length; 
    key = 10; 
  
    document.write( "Index: " + binarySearch(arr, 0, n - 1, key) 
    + "</br>"); 
      
      
</script>

Output

Index: 5

Time Complexity: O(log(n)) Using Binary Search
Auxiliary Space: O(log(n)) due to recursive calls, otherwise iterative version uses Auxiliary Space of O(1).

How to Insert in a Sorted Array?

In a sorted array, a search operation is performed for the possible position of the given element by using Binary search, and then an insert operation is performed followed by shifting the elements. And in an unsorted array, the insert operation is faster as compared to the sorted array because we don’t have to care about the position at which the element is placed.

Below is the implementation of the above approach:

C++

// C++ program to implement insert operation in 
// an sorted array. 
#include <bits/stdc++.h> 
using namespace std; 
  
// Inserts a key in arr[] of given capacity. n is current 
// size of arr[]. This function returns n+1 if insertion 
// is successful, else n. 
int insertSorted(int arr[], int n, int key, int capacity) 
{ 
    // Cannot insert more elements if n is already 
    // more than or equal to capacity 
    if (n >= capacity) 
        return n; 
  
    int i; 
    for (i = n - 1; (i >= 0 && arr[i] > key); i--) 
        arr[i + 1] = arr[i]; 
  
    arr[i + 1] = key; 
  
    return (n + 1); 
} 
  
/* Driver code */
int main() 
{ 
    int arr[20] = { 12, 16, 20, 40, 50, 70 }; 
    int capacity = sizeof(arr) / sizeof(arr[0]); 
    int n = 6; 
    int i, key = 26; 
  
    cout << "\nBefore Insertion: "; 
    for (i = 0; i < n; i++) 
        cout << arr[i] << " "; 
  
    // Function call 
    n = insertSorted(arr, n, key, capacity); 
  
    cout << "\nAfter Insertion: "; 
    for (i = 0; i < n; i++) 
        cout << arr[i] << " "; 
  
    return 0; 
} 
  
// This code is contributed by SHUBHAMSINGH10

C

// C program to implement insert operation in 
// an sorted array. 
#include <stdio.h> 
  
// Inserts a key in arr[] of given capacity.  n is current 
// size of arr[]. This function returns n+1 if insertion 
// is successful, else n. 
int insertSorted(int arr[], int n, int key, int capacity) 
{ 
    // Cannot insert more elements if n is already 
    // more than or equal to capacity 
    if (n >= capacity) 
        return n; 
  
    int i; 
    for (i = n - 1; (i >= 0 && arr[i] > key); i--) 
        arr[i + 1] = arr[i]; 
  
    arr[i + 1] = key; 
  
    return (n + 1); 
} 
  
/* Driver code */
int main() 
{ 
    int arr[20] = { 12, 16, 20, 40, 50, 70 }; 
    int capacity = sizeof(arr) / sizeof(arr[0]); 
    int n = 6; 
    int i, key = 26; 
  
    printf("\nBefore Insertion: "); 
    for (i = 0; i < n; i++) 
        printf("%d  ", arr[i]); 
  
    // Function call 
    n = insertSorted(arr, n, key, capacity); 
  
    printf("\nAfter Insertion: "); 
    for (i = 0; i < n; i++) 
        printf("%d  ", arr[i]); 
  
    return 0; 
}

Java

// Java program to insert an 
// element in a sorted array 
  
class Main { 
    // Inserts a key in arr[] of given 
    // capacity.  n is current size of arr[]. 
    // This function returns n+1 if insertion 
    // is successful, else n. 
    static int insertSorted(int arr[], int n, int key, 
                            int capacity) 
    { 
        // Cannot insert more elements if n is already 
        // more than or equal to capacity 
        if (n >= capacity) 
            return n; 
  
        int i; 
        for (i = n - 1; (i >= 0 && arr[i] > key); i--) 
            arr[i + 1] = arr[i]; 
  
        arr[i + 1] = key; 
  
        return (n + 1); 
    } 
  
    /* Driver code */
    public static void main(String[] args) 
    { 
        int arr[] = new int[20]; 
        arr[0] = 12; 
        arr[1] = 16; 
        arr[2] = 20; 
        arr[3] = 40; 
        arr[4] = 50; 
        arr[5] = 70; 
        int capacity = arr.length; 
        int n = 6; 
        int key = 26; 
  
        System.out.print("\nBefore Insertion: "); 
        for (int i = 0; i < n; i++) 
            System.out.print(arr[i] + " "); 
  
        // Function call 
        n = insertSorted(arr, n, key, capacity); 
  
        System.out.print("\nAfter Insertion: "); 
        for (int i = 0; i < n; i++) 
            System.out.print(arr[i] + " "); 
    } 
}

Python3

# Python3 program to implement insert 
# operation in an sorted array. 
  
# Inserts a key in arr[] of given capacity. 
# n is current size of arr[]. This function 
# returns n+1 if insertion is successful, else n. 
  
  
def insertSorted(arr, n, key, capacity): 
  
    # Cannot insert more elements if n is 
    # already more than or equal to capacity 
    if (n >= capacity): 
        return n 
  
    i = n - 1
    while i >= 0 and arr[i] > key: 
        arr[i + 1] = arr[i] 
        i -= 1
  
    arr[i + 1] = key 
  
    return (n + 1) 
  
  
# Driver Code 
if __name__ == "__main__": 
    arr = [12, 16, 20, 40, 50, 70] 
  
    for i in range(20): 
        arr.append(0) 
  
    capacity = len(arr) 
    n = 6
    key = 26
  
    print("Before Insertion: ", end=" ") 
    for i in range(n): 
        print(arr[i], end=" ") 
  
    # Function call 
    n = insertSorted(arr, n, key, capacity) 
  
    print("\nAfter Insertion: ", end="") 
    for i in range(n): 
        print(arr[i], end=" ") 
  
# This code is contributed by Mohit Kumar 

C#

using System; 
  
// C# program to insert an 
// element in a sorted array 
  
public class GFG { 
  
    // Inserts a key in arr[] of given 
    // capacity.  n is current size of arr[]. 
    // This function returns n+1 if insertion 
    // is successful, else n. 
    public static int insertSorted(int[] arr, int n, 
                                   int key, int capacity) 
    { 
        // Cannot insert more elements if n is already 
        // more than or equal to capacity 
        if (n >= capacity) { 
            return n; 
        } 
  
        int i; 
        for (i = n - 1; (i >= 0 && arr[i] > key); i--) { 
            arr[i + 1] = arr[i]; 
        } 
  
        arr[i + 1] = key; 
  
        return (n + 1); 
    } 
  
    /* Driver code */
    public static void Main(string[] args) 
    { 
        int[] arr = new int[20]; 
        arr[0] = 12; 
        arr[1] = 16; 
        arr[2] = 20; 
        arr[3] = 40; 
        arr[4] = 50; 
        arr[5] = 70; 
        int capacity = arr.Length; 
        int n = 6; 
        int key = 26; 
  
        Console.Write("\nBefore Insertion: "); 
        for (int i = 0; i < n; i++) { 
            Console.Write(arr[i] + " "); 
        } 
  
        // Function call 
        n = insertSorted(arr, n, key, capacity); 
  
        Console.Write("\nAfter Insertion: "); 
        for (int i = 0; i < n; i++) { 
            Console.Write(arr[i] + " "); 
        } 
    } 
} 
  
// This code is contributed by Shrikant13

Javascript

<script> 
  
// JavaScript program to insert an 
// element in a sorted array 
    // Inserts a key in arr[] of given 
    // capacity.  n is current size of arr[]. 
    // This function returns n+1 if insertion 
    // is successful, else n. 
    function insertSorted( arr, n, key, capacity) 
    { 
      
        // Cannot insert more elements if n is already 
        // more than or equal to capacity 
        if (n >= capacity) 
            return n; 
  
        var i; 
        for (i = n - 1; (i >= 0 && arr[i] > key); i--) 
            arr[i + 1] = arr[i]; 
  
        arr[i + 1] = key; 
  
        return (n + 1); 
    } 
  
    /* Driver program to test above function */
        var arr = new Array(20); 
        arr[0] = 12; 
        arr[1] = 16; 
        arr[2] = 20; 
        arr[3] = 40; 
        arr[4] = 50; 
        arr[5] = 70; 
        var capacity = arr.length; 
        var n = 6; 
        var key = 26; 
  
        document.write("\nBefore Insertion: "); 
        for (var i = 0; i < n; i++) 
            document.write(arr[i] + " "); 
  
        // Inserting key 
        n = insertSorted(arr, n, key, capacity); 
  
        document.write("<br>" +"\nAfter Insertion: "); 
        for (var i = 0; i < n; i++) 
            document.write(arr[i] + " "); 
              
  // This code is contributed by shivanisinghss2110   
</script>

Output

Before Insertion: 12 16 20 40 50 70 
After Insertion: 12 16 20 26 40 50 70

Time Complexity: O(N) [In the worst case all elements may have to be moved]
Auxiliary Space: O(1)

How to Delete in a Sorted Array?

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

GeeksforGeeks

Improve

Previous Article

Search, Insert, and Delete in an Unsorted Array | Array Operations

Array | Sorting

Similar Reads

Search, Insert, and Delete in an Unsorted Array | Array Operations

In this post, a program to search, insert, and delete operations in an unsorted array is discussed. Search Operation:In an unsorted array, the search operation can be performed by linear traversal from the first element to the last element. Coding implementation of the search operation: C/C++ Code // C++ program to implement linear // search in uns

Insert and delete element from spirally sorted matrix

Given a Spirally Sorted 2D matrix mat[][] of size NXN, remove an element R and add another element A with only one traversal and without disrupting the sorted order. In other words, the matrix should remain in a spirally sorted form after both removal and addition operations. Note: R will always be present in the Matrix to remove Examples: Input: m

Implementation of Search, Insert and Delete in Treap

We strongly recommend to refer set 1 as a prerequisite of this post.Treap (A Randomized Binary Search Tree)In this post, implementations of search, insert and delete are discussed.Search: Same as standard BST search. Priority is not considered for search. C/C++ Code // C function to search a given key in a given BST TreapNode* search(TreapNode* roo

Design a data structure that supports insert, delete, search and getRandom in constant time

Design a data structure that supports the following operations in O(1) time. insert(x): Inserts an item x to the data structure if not already present.remove(x): Removes item x from the data structure if present. search(x): Searches an item x in the data structure.getRandom(): Returns a random element from the current set of elements We can use has

Minimum cost to convert one given string to another using swap, insert or delete operations

Given two strings A and B of length N and M respectively, the task is to find the minimum cost to convert string A to B using the following operations: A character of string A can be swapped from another character of the same string. Cost = 0.A character can be deleted from string B or can be inserted in the string A. Cost = 1. Examples: Input: A =

Search insert position of K in a sorted array

Given a sorted array arr[] consisting of N distinct integers and an integer K, the task is to find the index of K, if it's present in the array arr[]. Otherwise, find the index where K must be inserted to keep the array sorted. Examples: Input: arr[] = {1, 3, 5, 6}, K = 5Output: 2Explanation: Since 5 is found at index 2 as arr[2] = 5, the output is

Given a linked list which is sorted, how will you insert in sorted way

Given a sorted linked list and a value to insert, write a function to insert the value in a sorted way.Initial Linked List Linked List after insertion of 9 Recommended PracticeInsert in a Sorted ListTry It! Algorithm: Let input linked list is sorted in increasing order. 1) If Linked list is empty then make the node as head and return it. 2) If the

Insert value in sorted way in a sorted doubly linked list

Given a sorted doubly linked list and a value to insert, write a function to insert the value in sorted way.Initial doubly linked list Doubly Linked List after insertion of 9 Recommended PracticeInsert in Sorted way in a Sorted DLLTry It! Algorithm: Let input doubly linked list is sorted in increasing order. New node passed to the function contains

Implement the insert and delete functions on Priority queue without Array

A priority Queue is a type of queue in which every element is associated with a priority and is served according to its priority. We will use two popular data structures for implementing priority queues without arrays - Fibonacci HeapBinomial HeapFibonacci Heap:Fibonacci heap is a heap data structure that is composed of a collection of min-heap-ord

Queries to insert, delete one occurrence of a number and print the least and most frequent element

Given Q queries of type 1, 2, 3 and 4 as described below. Type-1: Insert a number to the list.Type-2: Delete only one occurrence of a number if exists.Type-3: Print the least frequent element, if multiple elements exist then print the greatest among them.Type-4: Print the most frequent element, if multiple elements exist then print the smallest amo

Article Tags :

Practice Tags :