# 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.

- If

- 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

- the new upper index is
- If
`arr[midpoint]<T`

- the new lower index is
`midpoint+1`

- re-use the current iteration’s upper index

- the new lower index is

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)

- (we already checked that
- 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.