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.

binary_search:
    A = starting point of an array
    value = value to search for
    n = number of items to search

    if n <= 0:
        return NOT FOUND

    half = floor of n / 2

    if A[half] equals value:
        return A[half]

    if value is greater than A[half]
        return binary_search(A[half + 1], n - half - 1)

    // if it isn't greater or equal, it must be less than
    return binary_search(A[0], half)

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions

Advantages

  • Array Advantages: All of the advantages of standard arrays
  • Search: Optimized for quick search operations
  • Utility: Many useful operations beyond standard arrays

Disadvantages

  • Insert\Delete: Virtually unsupported because the array would either need to be resorted, or all the items would need to be shifted in memory.
  • 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.