Interview Prep: Binary Search

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:

```py
def binary_search( value : ComparableT, items : Sequence[ComparableT] )
-> Optional[int]:
```

You should assume the array is sorted.

Upper and Lower Bound

For extra credits, write the upper and lower bound functions.

`lower_bound` returns the first index where the item in the list is not less than the input value.

`upper_bound` 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: https://github.com/mortoray/interview.codes/tree/master/binary-search