Table of Contents
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): return -1 # x is not found 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] = x #add x 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) if index == -1: #element not found print("Element not found") 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.

Blog Hero