Array Basics
excerpt: Find, Minimum, Maximum, Average, Median, Insert and Remove tags: linearscan valuecomparison pairwisecomparison
In an unsorted array, finding an item requires performing a linear search or exhautive search. Look at every element in the array until the target item is either found or conclude that it is not in the array.
Finding Items
The index
method searches for the target item by searching through all the elements in the array, it returns the index of the target if it is found otherwise, it returns 1.


In the worst case, the target item may be the last item in the array. The time complexity is O(N). The wors case also occurs if the target item is not in the array.
Minimum, Maximum and Average
Calculating the minimum, maximum and average requires us to traverse the entire array.


Calculating the maximum in an array:


Caculcating the average in an array:


The length of the array is multipled by 1.0 to prevent rounding errors.
Median
The median is the value that lies in the middle of the values when the array is sorted. For example, the median of 1,3,4,7,8,8,9 is 7 because there three smaller values (1,3,4) and three larger values (8,8,9).
A single pass through the array does not give us all the information we need to calculate the median, because we need more global information about the values to find the median.
One approach is to think about each value in the list. For each test value, reconsider all the values and keep track of those that are larger and smaller than the test value. If a test value is found to have equal number of smaller and larger entries, the test value is the median.


This implementation does not handle the case in which multiple items have the same value, as in 1,2,3,3,4. It also does not handle arrays with an even number of items, which have no item in the middle. If an array has an even number of items, its median is defined as the average of the two middlemost items. For example, the median of 1,4,6,9 is 4+6/2 = 5. The time complexity is quadratic.
A much faster algorithm is to first sort the array and then find the median directly by looking at the values in the sorted array. Sorting takes O(n log n) time which is a lot faster than quadratic time.
Inserting Elements
Inserting an element at the end of an array is easy if the programming language can extend the array by one item. Inserting an element anywhere else is not easy. The insert
method inserts a new item at location position
in an array.


The array size is increased by one by appending the last element to the end of the array. The elements that are after the position
index are shifted once to the right and the new element is inserted in the index value of the position
.
The loop starts at the end of the array and moves toward the beginning. The elements are copied to the next location that is on the right of its previous position. The loop executes n  position times where n is the size of the array. In the worst case, adding an item to the beginning of the array, position = 0, the loop executes n times, so the time complexity is O(N).
Inserting elements is not common, but the technique of shifting elements in an array to make room for a new one is useful in other algorithms.
Removing Items
The elements that come after the position k moves one position closer to the beginning of the array. The array is resized to remove the final unused entry.


In the worst case, removing the first item from the array, all the items must be moved in the array. In this case, the time complexity is O(N).