0
306

# Search, insert and delete in an unsorted array

In this post search, insert and delete operation 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.

`// C program to implement linear search in `
`// unsorted array`
`#include<stdio.h>`
`/* Function to implement search operation */`
`int` `findElement(``int` `arr[], ``int` `n,``int` `key)`
`{`
`    ``int` `i;`
`    ``for` `(i=0; i<n; i++)`
`        ``if` `(arr[i] == key)`
`            ``return` `i;`
`    ``return` `-1;`
`}`
`/* Driver program to test above function */`
`int` `main()`
`{`
`    ``int` `arr[] = {12, 34, 10, 6, 40};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr);`
`    ``//Using a last element as search element`
`    ``int` `key =40;`
`    ``int` `position = findElement(arr,n,key);`
`    ``if` `(position==-1)`
`        ``printf``(``"Element not found"``);`
`    ``else`
`        ``printf``(``"Element Found at Position: %d"``, position+1 );`
`    ``return` `0;`
`}`

Output:

```Element Found at Position: 5
```

Insert Operation

In an unsorted array, the insert operation is faster as compared to sorted array because we don’t have to care about the position at which the element is to be placed.

`// C program to implement insert operation in`
`// an unsorted 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 capcity`
`    ``if` `(n >= capacity)`
`       ``return` `n;`
`    ``arr[n] = key;`
`    ``return` `(n+1);`
`}`
`/* Driver program to test above function */`
`int` `main()`
`{`
`    ``int` `arr = {12, 16, 20, 40, 50, 70};`
`    ``int` `capacity = ``sizeof``(arr)/``sizeof``(arr);`
`    ``int` `n = 6;`
`    ``int` `i, key = 26;`
`    ``printf``(``"\nBefore Insertion: "``);`
`    ``for` `(i=0; i<n; i++)`
`        ``printf``(``"%d  "``, arr[i]);`
`    ``// Inserting key`
`    ``n = insertSorted(arr, n, key, capacity);`
`    ``printf``(``"\nAfter Insertion: "``);`
`    ``for` `(i=0; i<n; i++)`
`        ``printf``(``"%d  "``,arr[i]);`
`    ``return` `0;`
`}`

Output:

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

Delete Operation

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

`// C program to implement delete operation in a`
`// unsorted array`
`#include<stdio.h>`
`// To search a key to be deleted`
`int` `findElement(``int` `arr[], ``int` `n, ``int` `key);`
`/* Function to delete an element */`
`int` `deleteElement(``int` `arr[], ``int` `n, ``int` `key)`
`{`
`    ``// Find position of element to be deleted`
`    ``int` `pos = findElement(arr, n, 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;`
`}`
`/* Function to implement search operation */`
`int` `findElement(``int` `arr[], ``int` `n, ``int` `key)`
`{`
`    ``int` `i;`
`    ``for` `(i=0; i<n; i++)`
`        ``if` `(arr[i] == key)`
`            ``return` `i;`
`    ``return` `-1;`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``int` `i;`
`    ``int` `arr[] = {10, 50, 30, 40, 20};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr);`
`    ``int` `key = 30;`
`    ``printf``(``"Array before deletion\n"``);`
`    ``for` `(i=0; i<n; i++)`
`      ``printf``(``"%d  "``, arr[i]);`
`    ``n = deleteElement(arr, n, key);`
`    ``printf``(``"\n\nArray after deletion\n"``);`
`    ``for` `(i=0; i<n; i++)`
`      ``printf``(``"%d  "``, arr[i]);`
`    ``return` `0;`
`}`

Output:

```Array before deletion
10 50 30 40 20

Array after deletion
10 50 40 20
```

Time complexities:
Search: O(n)
Insert: O(1)
Delete: O(n)