# Implementation of Sorted Arrays

As the name suggests, a sorted array has all the elements sorted in a specific order, such as numerical or alphabetical order. One of the main advantages of the sorted array is that it makes the search operation very efficient. We can perform the lookup in `O(logn)` time by applying the binary search algorithm. However, the time complexity of insertion and deletion is `O(n)` as we have to shift items.

## How to Implement a Sorted Array?

```def binarySearch(array, x, start, end):
if (end < start):
mid = (start+end)//2 #find the mid
if (x==array[mid]): #if x is equal to middle element
return mid
elif (x> array[mid]): # x lies in the upper half
return binarySearch(array, x, mid+1, end)
else: # x lies in the lower half
return binarySearch(array, x, start, mid-1)

def insert(array, x):

n = len(array)
if x>=array[n-1]: #add element at the end
array.append(x)
return array

for i in range(0, n):
if x < array[i]:
sliced_array = array[i:] #copy the elements greater than x
break

array[i+1:]=sliced_array #put the remaining elements
return array

def delete(array, x):
n = len(array)
index = binarySearch(array, x, 0, n-1)

return -1

if index == n-1: #deleting the last element
return array[0: n-1]

elif index ==0: #deleting the first element
return array[1:n]

else:
left = array[0:index] #items before the index
right = array[index+1:] #items after the index
left.extend(right) #combining
return left
```

## Operations on Sorted Arrays

### Search

As already mentioned, we perform the lookup operation using the binary search algorithm. The method checks if the given element is equal to the middle value, and in that case, its index gets returned. If it is greater than the middle value, it means that the element can lie in the upper half, so only that part gets considered. If it is less than the middle value, it can exist in the lower half.

```scores = [50, 75.5, 85, 90, 91.5]
n = len(scores)
index = binarySearch(scores, 90, 0, n-1)
if index!=1:
print(f"Element found at index {index}")
```

Output

Element found at index 3

### Insertion

The `insert()` method checks whether an element is greater than the last value or not. If it is, it will get appended to the list, and no shifting is required. Otherwise, it iterates through the array until it finds the greater than `x`. The x will get inserted at that index, and the rest of the elements will get shifted. Therefore, we copy the rest of the items and break from the loop. Finally, we add `x` at its position and put the remaining elements after that.

```scores = [50, 75.5, 85, 90, 91.5]
n = len(scores)
scores = insert(scores, 100)
scores = insert(scores, 49.6)
scores = insert(scores, 70)
print(scores)
```

Output

[49.6, 50, 70, 75.5, 85, 90, 91.5, 100]

### Delete

The `delete()` method finds the index of the input element if it exists in the array, then removes it by slicing the array depending upon the item’s position.

```scores = [50, 75.5, 85, 90, 91.5]
n = len(scores)
scores = delete(scores, 85)
print(scores)
```

Output

[50, 75.5, 90, 91.5]

Concluding, sorted arrays are useful in those cases where the frequency of the lookup operation is more than insertion and deletion operations.

Back to: Data Structure > Data Structure - Arrays