Search, Insert, and Delete in an Unsorted Array

Here’s a detailed explanation of the search, insert, and delete operations in an unsorted array, along with their time and space complexities, and implementations in C++, Java, and Python.

1. Search Operation

Algorithm:

• Iterate through each element of the array.

• Compare the current element with the target.

• If a match is found, return the index.

• If the loop completes without finding the element, return a flag indicating that the element is not present.

Time Complexity:

• Best Case: O(1) (element is the first element)

• Worst Case: O(n) (element is not present or is the last element)

Space Complexity:

• O(1) (no extra space is used apart from a few variables)

Example Code:

• C++:

    int search(int arr[], int n, int key) {
        for (int i = 0; i < n; i++) {
            if (arr[i] == key)
                return i;
        }
        return -1; // Element not found
    }
  

• Java:

    ublic static int search(int[] arr, int n, int key) {
        for (int i = 0; i < n; i++) {
            if (arr[i] == key)
                return i;
        }
        return -1; // Element not found
    }
  

• Python:

    def search(arr, n, key):
        for i in range(n):
            if arr[i] == key:
                return i
        return -1  # Element not found
  

2. Insert Operation

Algorithm:

• Insert the new element at the end of the array.

Time Complexity:

• Average Case: O(1)

• Worst Case: O(1)

Space Complexity:

• O(1) if space is preallocated for the array size.

Example Code:

• C++:

    void insert(int arr[], int &n, int element, int capacity) {
        if (n < capacity) {
            arr[n] = element;
            n++;
        }
    }
  

• Java:

    public static void insert(int[] arr, int n, int element, int capacity) {
        if (n < capacity) {
            arr[n] = element;
            n++;
        }
    }
  

• Python:

    def insert(arr, n, element):
        arr.append(element)
        return n + 1
  

3. Delete Operation

Algorithm:

• Search for the element.

• If found, swap it with the last element.

• Reduce the size of the array by one.

Time Complexity:

• Search: O(n)

• Deletion: O(1) (after finding the element)

Space Complexity:

• O(1) (no extra space is used)

Example Code:

• C++:

    void deleteElement(int arr[], int &n, int key) {
        int pos = search(arr, n, key);
        if (pos == -1) {
            return; // Element not found
        }
        arr[pos] = arr[n - 1]; // Swap with the last element
        n--; // Reduce the size
    }
  

• Java:

    public static void deleteElement(int[] arr, int n, int key) {
        int pos = search(arr, n, key);
        if (pos == -1) {
            return; // Element not found
        }
        arr[pos] = arr[n - 1]; // Swap with the last element
        n--; // Reduce the size
    }
  

• Python:

    edef deleteElement(arr, n, key):
        pos = search(arr, n, key)
        if pos == -1:
            return n  # Element not found
        arr[pos] = arr[-1]  # Swap with the last element
        arr.pop()  # Remove the last element
        return n - 1
  

Summary of Complexities

These implementations and explanations should give you a clear understanding of how to perform search, insert, and delete operations in an unsorted array.