# Sorted Array

A sorted array has considerably more utility than a standard array. Because of this, sorting algorithms are one of the most scrutinized areas of computer science. Sorted arrays are an excellent option in cases where the data is well defined and does not require inserts and deletes. Insert and delete operations are especially onerous because they require a complete rearrangement of data in memory. Sorting an array enables all of these extra abilities:

1. Min - Find the minimum value in the array
2. Max - Find the maximum value in an array
3. Predecessor - Find the item directly before an arbitrary item
4. Successor - Find the item directly after an arbitrary item
5. Rank - Find the rank of any specific item

In addition to the added utility, search operations go from linear to logarithmic time. That’s a considerable gain. The efficiency is achieved by using a special algorithm called binary search that only works on sorted content. This is an important algorithm to understand because of it’s ubiquity.

## Asymptotic Complexity

• Search: $O(\log_{2}n)$
• Enumerate: $O(n)$
• Min: $O(1)$
• Max: $O(1)$
• Predecessor: $O(\log_{2}n)$
• Successor: $O(\log_{2}n)$
• Select: $O(1)$
• Rank: $O(\log_{2}n)$

## Pseudo Code

Binary Search is the only operation for which pseudo code is provided because the rest are fairly self explanatory by pursuing the provided source code.

\begin{algorithm}
\caption{Binary Search}
\begin{algorithmic}
\REQUIRE A = list of values sorted sequentially
\REQUIRE value = value to search for
\OUTPUT value if it exists, otherwise -1
\FUNCTION{binarySearch}{A, value}
\IF{$\vert A \vert \leq 0$}
\RETURN -1
\ENDIF
\STATE half $\gets \lfloor\frac{\vert A \vert}{2}\rfloor$
\IF{$A_{half} =$ value}
\RETURN $A_{half}$
\ENDIF
\IF{$A_{half} \gt$ value}
\RETURN \CALL{binarySearch}{$A_{half + 1}...A_{\vert A \vert - 1}$, value}
\ENDIF
\RETURN \CALL{binarySearch}{$A_0...A_{half-1}$, value}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}


## Source Code

Full Repo

Relevant Files:

• Sort Time: The fastest an array can be sorted is $O(n \lg_{2}n)$. This time must be calculated into any algorithm hoping to capitalize on the added utility.