A binary search essentially divides a sorted array in half, recursively, narrowing down a list of possible elements that match the value provided. That's it, honestly. It's such a simple idea -- just pick a point in the middle of an array, if the searched value is bigger than the point you picked, search the right half; otherwise, search the left. Repeat this procedure until you've found the value you're looking for.

How about we visualize this with an example. You have an array with values `[1, 3, 4, 5, 8, 10, 15, 18, 20, 21, 22]`

, and you're searching for `15`

. here's how it works:

`[1, 3, 4, 5, 8, 10*(start here), 15, 18, 20, 21, 22]`

`15`

is >`5`

. so lets check the right half

`[15, 18, 20*(middle of right side), 21, 22]`

`15`

is < than`20`

. so lets go left

`[15*(start here), 18]`

- well what do you know, 15 is our match!!

Since the binary search recursivley cuts our possible matches in half, it is a logarithmic algorithm. Big O notation of O(log N+1) at worst case.

A great example of the binary search in practice is git-bisect. Git Bisect is a tool that performs a recursive binary search on a list of commits in order to find a bug-introducing commit. Git-Bisect is really great and I suggest you use it whenever you can!

Lets check out an example of binary search in ES6:

```
function binarySearch(array, val){
'use strict';
let minimumIndex = 0;
let maxIndex = array.length - 1;
let currentIndex;
(function search(){
currentIndex = Math.floor((minimumIndex + maxIndex) / 2);
console.log(`curently looking between ${array[minimumIndex]} and ${array[maxIndex]}`);
if (array[currentIndex] === val ){
console.log(`FOUND IT! ${val} == ${array[currentIndex]}`);
return;
}
if (val > array[currentIndex]){
minimumIndex = currentIndex + 1;
}
if (val < array[currentIndex]){
maxIndex = currentIndex -1;
}
search();
})();
}
module.exports = {binarySearch};
```

Our ES6 code should be pretty straightforward here, but lets break it down:

- we create a few variables to set up our search. Our minimumIndex, and maximumIndex respectively. And a current index.
- we create a named IIFE to do all our recursion.
- we set our current index to whatever our bounds are (min and max index) divided by 2, rounded down.
- if the searched value is greater than current index, move our min index up
`currentIndex + 1`

- if our searched value is smaller than current index, move our max index to
`currentIndex - 1`

.

And we repeat this until we find our match.

Lets see what this looks like in node:

```
js-cs-notes master % node
> let search = require('./binary-search');
> let arr = [1, 3, 4, 5, 8, 10, 15, 18, 20, 21, 22];
> let val = 15;
> search.binarySearch(arr, val);
curently looking between 1 and 22
curently looking between 15 and 22
curently looking between 15 and 18
FOUND IT! 15 == 15
```

And there you have it. A basic implementation of binary-search in ES6. I hope you found this at least half as fun as I did. Thank you!

]]>