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
high which will be the boundaries of the indices we are seraching for
We start off by defining the
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
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
mid, so we can change
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,
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)).
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
contains function is pretty easy.
In this implementation, I call
_binarySeach inside the function.
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!