Ordered (sorted) array

- data is ordered (sorted) in ascending (or descending) key order which enables fast search algorithm - binary search (this is the main reason why we want to keep data sorted)
- can be searched with linear search as well

Binary Search Algorithm

Take the idem from the middle of the range (array of sorted elements). If its value is smaller than the searched value then take right sub-array as a new range and repeat this step.

The range will eventually drop to only one member and if its value matches the searched one - item is found.

As in each new iteration range size is halved, the complexity of the algorithm is O(logN). If we double the number of elements, we would need only one extra iteration.

Operations

Insertion:

- Algorithm: linear search is needed to find the first element smaller than the one to be inserted; item is inserted after it and all bigger items are shifted one place towards the end

- Complexity: O(N) (linear search) + O(N) (shifting) = 2 * O(N) ~ O(N)

Search:

- Algorithm: binary search

- Complexity: O(logN) 

Deletion:

- Algorithm: binary search to find the element; once it's found it is removed and all subsequent elements are shifted towards the array beginning

- Complexity: O(logN)(binary search) + O(N) (shifting) ~ O(N)