Linear and Binary Search in JavaScript
Tags: javascript, computerscience, binarysearch
Published: 2018-05-16 23:55:43

---
title: Linear and Binary Search in JavaScript
published: true
description: 
tags: javascript, computerscience, binarysearch
---

This week I started reading Grokking's [Algorithms](https://www.manning.com/books/grokking-algorithms), an illustrated guide for programmers and other curious people. So far it's a fantastic read -- full of practical examples with fun drawings to explain technical concepts in understandable ways. Code examples in the book are written in Python. I'm primarily a JavaScript developer, so I thought I'd work my way through the book and show you my JavaScript code.

## Searching through Arrays
You're searching for something in a list. You aren't sure if it is actually in the list, but if it is, you'd like to know where it is. In this case we have a rainbow and we are looking for a specific color.
```javascript
var rainbow = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"];
```

#### The ~~Easy~~   ~~Bad~~ Linear Way

You may be thinking, "Easy! I'll just loop through each element of the array and return the match!" This works, and is called a linear search.

```javascript
function linearSearch(arr, elToFind) {
  for (var i=0; i<arr.length; i++) {
    if (arr[i] == elToFind) {
      return i;
    }
  } return null;
}

linearSearch(rainbow, "green"); // returns 3
linearSearch(rainbow, "white"); // returns null
```
Buttttttt, (and the size of this but is dependent on the size of your data set) there's a performance tradeoff here. You have to loop through every single element to find out that yours isn't part of the array. When we are only talking 7 colors, this is nbd but what if we were going through an array of thousands or millions of records? [Forget it.](https://media.giphy.com/media/1DagSuFvJ1BlK/giphy.gif)

#### Binary Search
 A [binary search](https://en.wikipedia.org/wiki/Binary_search_algorithm) takes in a sorted array and looks for a specific element. If the element is present in the array, the search returns the index of the element; otherwise it returns null. Because the array has already been sorted, the search can compare the target search element to the element in the middle of the array, eliminating half the search range at a time. Think of it as a game of hotter-colder.

![alt text](https://upload.wikimedia.org/wikipedia/commons/thumb/8/83/Binary_Search_Depiction.svg/470px-Binary_Search_Depiction.svg.png "binary search image from Wikipedia")

#### Retrying the Rainbow Example with Binary Search
You and I understand the ROY G. BIV ordering of the aforementioned rainbow, but your browser didn't go to Kindergarten. In order to perform a binary search on the rainbow, it needs to be (alphabetically) sorted. Luckily, we have JavaScript's built in sort method for arrays.
```javascript
var rainbow = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"];
var sortedRainbow = rainbow.sort(); 
// returns ["blue", "green", "indigo", "orange", "red", "violet", "yellow"];
```
Great! Now we have something we can pass a to  binary search.

```javascript
function binarySearch(sortedArray, elToFind) {
  var lowIndex = 0;
  var highIndex = sortedArray.length - 1;
  while (lowIndex <= highIndex) {
    var midIndex = Math.floor((lowIndex + highIndex) / 2);
    if (sortedArray[midIndex] == elToFind) {
      return midIndex;
    } else if (sortedArray[midIndex] < elToFind) {
      lowIndex = midIndex + 1;
    } else {
      highIndex = midIndex - 1;
    }
  } return null;
}

var sortedRainbow = ["blue", "green", "indigo", "orange", "red", "violet", "yellow"];
binarySearch(sortedRainbow, "green"); // returns 1
binarySearch(sortedRainbow, "white") // returns null
```
Okay, that was a lot. Or maybe you're a search whiz and you completely understood that. Let's take the binary search line by line. 
- The **binarySearch** function takes in a **sortedArray** and an element you are searching for (**elToFind**). 
	- During the search, you'll be keeping track of the range you are searching through with a starting **lowIndex** of 0 and a starting **highIndex** of the number of elements in the sorted array. At the start of the search, the range will span the entire array.
	- the **while** loop executes until the search has been narrowed to one element
		- to find the index of the element between the **lowIndex** and the **highIndex**, average these two value (Note: use Math.floor to round this value down because the **midIndex** must be an integer)

		- if you've found the element, return the index
		- if the current element is less than (alphabetically before) the element you're searching for, increase the **lowIndex** to one more than the **midIndex**
		- if the current element is greater than (alphabetically after) the element you're searching for, decrease the **highIndex** to one less than the **midIndex**
	- if the element doesn't exist in the array, return null


### Up Next

Now that we've looked at two search methods (linear and binary) we need a way to measure their performance against one another. In my next post I'll look at  logarithms (throwback to Algebra 2) and Big O notation. Stay tuned!