15 Dec 2017

Binary Search

Click the result tab on the codepen to see it in action.

Binary search is an algorithm used to find the position of an item in a sorted array.

Given array arr and target T, we divide and conquer to search for the index of a target value by iteratively applying the following operations (L and R are the lower and upper bounds of the search space, inclusive):

Find the midpoint of the subarray arr.slice(L, R)

On the first run of the algorithm, L=0 and R=arr.length-1
On subsequent runs, we use previous values of L and R as the search space narrows
Midpoint will be Math.min((L+R)/2)

Compare arr[midpoint] to T.
If arr[midpoint]===T we found the index. Return the index midpoint.
Else, T is either to the “right” (greater than) or the “left” (less than) of the current midpoint.

Since we assume the array is sorted, we can determine which half T lies in.
- If arr[midpoint]>T, then T lies in the lower half
- Else, T lies in the upper half.

We adjust the search space accordingly.

If arr[midpoint]>T
- the new upper index is midpoint-1
- re-use the current iteration’s lower index
If arr[midpoint]<T
- the new lower index is midpoint+1
- re-use the current iteration’s upper index

Each loop, check iteration quit conditions:

If L > R, the item does not exist in the array
If loop count is equal to the number of elements in the array, the item does not exist in the array (or the input is not sorted)

Before running the loop, we also exclude a few cases in which we cannot reasonably run the search.

If an array or target is not supplied, or if the array length is <=1
If the typeof target does not equal the typeof arr[0]
- (we already checked that arr exists so we know arr[0] is accessible)
If the typeof arr is not an array

aaaand a test runner!

We can also write a simple test runner to check the algorithm’s output.

A test runner is basically code that runs code and tells you what happened when it ran. Usually we have expectations about what code will do when it is given certain inputs, so you can supply the runner with these expectations, or expected results. The runner will run the code you provide with these inputs, compare them to the expected results, and then give you a list of code that passed (met the expected result) or failed (did not meet the expected result).

This test runner is simple: we hard-code in the function call, and for each test, we use .apply() (docs) to apply the arguments array to the function.

We record the function outputs and compare them to the expected results for each test.

Then, we’ll write a simple function to list out the description for each test, expected and actual results, and a pass or fail formatting based on whether the tests matched or failed to match expectations.