Data Structure Set 17

Search Operation
In a sorted array, the search operation can be performed by using binary search.
Input Format:
The first line of input consists of T, the number of test cases. T testcases follow. Each testcase contains 3 lines of input. The first line of every test case consists of an integer N, denotes the number of elements in an array. The second line of every test cases consists of N spaced integers A_i. and last the value to be search in array.
Time Complexity of Search Operation: O(Log n) [Using Binary Search] 

In a sorted array, a search operation is performed for the possible position of the given element by using Binary search and then 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 to be placed.
Example
Before Insertion: 12 16 20 40 50 70
26 to be add.
Output

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

Time Complexity of Insert Operation: O(n) [In the worst case all elements may have to be moved] 

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

Time Complexity of Delete Operation: O(n) [In the worst case all elements may have to be moved]