A sorted array is an array in which all elements are sorted. They are in ascending order by default. To add an element, it takes O(n) to find the right spot to insert. On the other hand, you can apply binary search to a sorted array to get performance gain from O(n) to O(logn).
Map of array implementations
Part 1 – Array implementation 
Part 2 – Sorted array implementation
Part 3 – Matrix 2d array implementation
Table of Content
Insert element in a sorted array
To insert an element in a sorted array, find the index of the position first. Then starting from the end to the index+1, move each element to its next position. Last put the value at the index.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
public class SortedArray<T extends Comparable<T>> { private T[] array; private int maxSize; private int length = 0; //Constructor, Time O(1), Space O(1) @SuppressWarnings("unchecked") public SortedArray(int size) { maxSize = size; array = (T[]) new Comparable[maxSize]; } public int compare(T a, T b ) throws ClassCastException { return a.compareTo( b ); } //Add one element, Time O(n), Space O(1), n is array length public void insert(T value) { if (length == maxSize) { System.out.println("reach max size!"); return; } int i = length-1; while (i >= 0 && array[i].compareTo(value) > 0) { array[i+1] = array[i]; i --; } array[i+1] = value; length ++; } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#Constructor, Time O(1), Space O(1) constructor() { this.length = 0; this.array = []; } //Add one element, Time O(n), Space O(1), n is array length insert(value) { var i = this.length -1; while (i >= 0 && this.array[i] > value) { this.array[i+1] = this.array[i] i --; } this.array[i+1] = value this.length ++; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class SortedArray: #Constructor, Time O(1), Space O(1) def __init__(self, size): self.num_items = 0 self.array = [None]*size self.max_size = size #Add one element, Time O(n), Space O(1), n is array length def insert(self, value): if self.num_items == self.max_size : print ("Reach max size, cannot add.") return i = self.num_items -1 while i >= 0 and self.array[i] > value: self.array[i+1] = self.array[i] i -= 1 self.array[i+1] = value self.num_items += 1 |
Doodle
Delete element
Starting from the end, move each element one position ahead until the index of the key.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//Delete by key, Time O(n), Space O(1) public boolean delete(T key) { int i = binarySearch(key); if (i < 0) { System.out.println("delete key not found"); return false; } else { for (int j = i; j < length-1; j++) array[j] = array[j+1]; length--; return true; } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//Delete by key, Time O(n), Space O(1) delete(key) { var i = this.binarySearch(key); if ( i < 0) { console.log("key not found"); return false; } else { for (let j = i; j < this.length-1; j++) this.array[j] = this.array[j+1]; this.length--; return true; } } |
Python
|
1 2 3 4 5 6 7 8 9 |
#Delete by key, Time O(n), Space O(1) def delete(self, key) : i = self.binary_search(key) if i < 0 : print("delete key not found") return for j in range (i, self.num_items-1): self.array[j] = self.array[j+1] self.num_items -= 1 |
Doodle
Binary search
Given the low and high positions, get the mid position. Compare the value of mid with the key, you can decide the new low and high position. Repeat until you find the key. Return the index of the key.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Binary search, Time O(logn), Space O(1) public int binarySearch(T key) { int low = 0; int high = length - 1; while (low <= high) { int mid = low + (high-low)/2; if (array[mid] == key) return mid; else if (key.compareTo(array[mid]) < 0) high = mid - 1; else low = mid + 1; } return -1; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Binary search, Time O(logn), Space O(1) binarySearch(key) { var low = 0; var high = this.length - 1; while (low <= high) { var mid = parseInt(low + (high-low)/2); if (this.array[mid] < key) low = mid + 1; else if (this.array[mid] > key) high = mid - 1; else return mid; } return -1; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#Binary search, Time O(logn), Space O(1) def binary_search(self, key) : low = 0 high = self.num_items - 1; while (low <= high) : mid = low + (high-low)//2 if self.array[mid] == key : return mid elif key < self.array[mid] : high = mid - 1 else : low = mid + 1 return -1 |
Doodle
Print elements
Print all elements in the array from index 0 to the last.
Java
|
1 2 3 4 5 6 |
//Print array, Time O(n), Space O(1) public void print( ) { for (int i = 0; i < length; i++) System.out.print(array[i] + " "); System.out.println(); } |
Javascript
|
1 2 3 4 5 6 7 8 |
//Print array, Time O(n), Space O(1) print() { var s = ''; for (var i = 0; i < this.length; i++) { s += this.array[i] + ' '; } console.log('array is ' + s); } |
Python
|
1 2 3 4 5 |
#Print array, Time O(n), Space O(1) def print(self) : for i in range(0, self.num_items): print(self.array[i], end = ' ' ) print() |
Doodle
Free download
Download Java, JavaScript and Python code
Data Structures Illustrated Java Book
Why sorting arrays?
When an array is sorted, you can apply binary search to find an element. The time complexity of binary search is O(logn). As n grows to millions and billions, binary search becomes especially fast. Binary search only applies to sorted arrays. So sorting data is usually the preliminary step of fast searching.