# Adventures in Data Structures Vol 9: Ordered Arrays and Binary Search

Exam review time already?? Time really flies.

Tonight, instead of spending the final day of the quarter at the bars, I’ll be spending it at home with a big thing of soup. Being in the midst of a pandemic isn’t great to say the least, but I suppose if I’m going to self-isolate, I can at least be a little productive haha.

# Binary Search in C

Today, I really wanted to go over ordered arrays and the binary search.

The main benefit to having *ordered collections* is that the **contains** operation is no longer a linear search!
Therefore, instead of being an O(n) operation, it is instead O(log n) which is **much faster**.
After all, consider that $log_2 1000000 \approx 20$.

The requirements for performing a binary search are that:

- The collection is ordered
- Random access to the elements is allowed

The binary search function in C will probably look something like this:

We have two integers `low`

and `high`

which will be the boundaries of the indices we are seraching for `val`

.
We start off by defining the `low`

and `high`

to be the indices at the ends of the collection.

Essentially what this function is doing is first finding the middle index of the sorted collection and assigning that to the variable `mid`

.
If the element at that middle index is *less than* the value we are searching for, then we can reassign `low`

to be `mid + 1`

since we know that the value we are searching for in contained somehwere inside that interval.

If that is not the case, then the value we are searching for is instead somewhere between `low`

and `mid`

, so we can change `high`

to `mid`

.
We then repeat this step until `low == high`

, at which point, we return an integer for the index where either `val`

is located **OR** where `val`

could be located if we were to insert it.

# Implementing an Ordered Bag

A dynamic array for an ordered bag is a pretty straightforward collection to implement.

Recall that a bag has the following operations: add, contains, and remove.
If we enforce the bag to keep elements in order, `add`

and `remove`

get slower and become O(n) since we have to slide elements over.
`Contains`

however gets much faster (O(log n) instead of O(n)).

The `add`

function doesn’t change too much, it just has to make use of the index outputted by the binary search function.
The rest is basically just the same as regular old bag `add`

function.

The `contains`

function is pretty easy.
In this implementation, I call `_binarySeach`

inside the function.

Finally, the `remove`

function is almost no different than the original implementation.
What we have to make sure of though is that the element at the index location is equal to the element we want to remove.

#### Last little note… Fast Merge

Merging two ordered arrays into a single new ordered array is also relatively fast at O(n). We basically compare the two ordered arrays pairwise to add elements into the single larger array. At the end, the larger array will be automatically sorted!