Sorted array is an array in which all elements are sorted. They are in ascending order by default. To add element, it takes O(n) to find the right spot to insert. On the other hand, we can apply binary search to sorted array to get performance gain from O(n) to O(logn).
Part 1 – Array implementation
Part 2 – Sorted array implementation
Part 3 – Matrix implementation
Table of Content
Insert element
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 their 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
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 ++; } //Find the location use binary search first, //Time O(n), Space O(1), n is array length public void insertOptimized (T value) { int i = findInsertIndex(value); for (int j = this.length; j > i; j--) this.array[j] = this.array[j-1]; this.array[i] = value; this.length++; } private int findInsertIndex(T value) { int low = 0, high = this.length; while (low < high) { int mid = low + (high-low)/2; if (array[mid].compareTo(value) < 0) low = mid + 1; else high = mid; } return low; } } |
Javascript
|
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 33 34 35 36 37 38 39 40 41 |
class SortedArray { //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 ++; } //Find the location use binary search first, //Time O(n), Space O(1), n is array length insertOptimized (value) { const i = this.findInsertIndex(value); for (let j = this.length; j > i; j--) this.array[j] = this.array[j-1]; this.array[i] = value; this.length++; } findInsertIndex(value) { var low = 0, high = this.length; while (low < high) { var mid = parseInt(low + (high-low)/2); if (this.array[mid] < value) low = mid + 1; else high = mid; } return low; } } |
Python
|
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 33 34 35 |
class SortedArray: #Constructor, Time O(1), Space O(1) def __init__(self): self.length = 0 self.array = {} #Add one element, Time O(n), Space O(1), n is array length def insert(self, value): i = self.length -1 while i >= 0 and self.array[i] > value: self.array[i+1] = self.array[i] i -= 1 self.array[i+1] = value self.length += 1 #Find the location use binary search first, #Time O(n), Space O(1), n is array length def insertOptimized (self, value) : i = self.findInsertIndex(value) for j in range (self.length, i, -1) : self.array[j] = self.array[j-1] self.array[i] = value self.length += 1 def findInsertIndex(self, value) : low = 0 high = self.length while low < high : mid = low + (high-low)//2 if self.array[mid] < value: low = mid + 1 else: high = mid return low |
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 10 11 |
#Delete by key, Time O(n), Space O(1) def delete(self, key) : i = self.binarySearch(key) if i < 0 : print("key not found") return False else : for j in range (i, self.length-1, +1): self.array[j] = self.array[j+1] self.length -= 1 return True |
Doodle
Binary search
Given the low and high position, 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 binarySearch(self, key) : low = 0 high = self.length - 1; while (low <= high) : mid = low + (high-low)//2 if self.array[mid] < key : low = mid + 1 elif self.array[mid] > key: high = mid - 1 else : return mid return -1 |
Doodle
Print elements
Print all element 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.length, +1): print(self.array[i], end = ' ' ) print() |
Doodle
Download Java, JavaScript and Python code
Data structures and Java collections