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.

Back to: Data Structure > Data Structure - Arrays