Description
 

A quick refresher of this common programming algorithm. Perfect for
interview preparation.

In this class, I look at the binary search algorithm. I walk through
some samples and provide the basic complexity analysis. In addition to
binary search, I explain lower and upper bound searching. You’ll learn
what they are and their purpose.


Project

I want you to write a binary search function. Pick a language and write
a function that takes an array of values, and an item to look for. The
function returns an optional value, the index of where the item is
found, or nothing if it wasn't found. If you're unfamiliar with optional
values, return a `-1` instead, should the value not be found.

In the example Python implementation, the signature looks like this:

<pre><code class>```py
def binary_search( value : ComparableT, items : Sequence[ComparableT] )
-> Optional[int]:
```</code></pre>

You should assume the array is sorted.

Upper and Lower Bound

For extra credits, write the upper and lower bound functions.

<code>`lower_bound`</code> returns the first index where the item in the list is not
less than the input value.

<code>`upper_bound`</code> returns the first index where the item in the list is
greater than the input value.
 
For all the algorithms, I provide a walkthrough of sample code. The code
is available for you to review.

Soure Code:
<a href="https://github.com/mortoray/interview.codes/tree/master/binary-search">https://github.com/mortoray/interview.codes/tree/master/binary-search</a>

Interview Prep: Binary Search

Back End

Description for Interview Prep: Binary Search