loading...

Linear and Binary Search in JavaScript

stephjs profile image Steph Updated on ・3 min read

This week I started reading Grokking's 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.

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.

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.

Binary Search

A binary search 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

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.

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.

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!

Discussion

pic
Editor guide
Collapse
bladefidz profile image
Hafidz Jazuli Luthfi

Hi, Stephanie...

I think, you may interested with this one. One year ago, when I want to understand C, I decided to do a very naive experiment to compare some classical sort algorithms. If you interested, you can read it at here.

It is very naive by the way, but if you have better idea how do similar experiments, that would be great.

Collapse
stephjs profile image
Steph Author

Hey Hafidz,

Cool! I'll give it a read. :) Was this a paper you wrote for school?

Collapse
bladefidz profile image
Hafidz Jazuli Luthfi

Thank you...

It just bonus assignment since a lecturer who teach algorithm course found that few of her student bored with the course (I think).

A mouth ago, I just realize that this empirical approach very useful in parallel programming. That's Gustavson Law that suggest us to use latency as benchmark.

Collapse
nodefiend profile image
chowderhead

love this steph!

great post !

at our company(startup) we deal with large data sets that are only getting larger and implementing this on our backend (rails api) will really speed up our methods!

thanks so much

Collapse
poxrud profile image
Phil

FYI ruby has already a built in binary search.

Collapse
linaran profile image
Deni

Linear searches are slower than binary searches but they aren't inherently bad and binary searches aren't always better.

If you have a use case where you often need to add elements to your array, keeping your array sorted can be very expensive. Sorting algorithms are usually O(n*log n) complexity and that may be slower than performing a simple linear search on your array.

So depending on your use case linear search can be perfectly fine.

Collapse
stephjs profile image
Steph Author

That's true, it depends on your data set. Assuming it's sorted and you're only worried about the run time of the search, a linear search is O(n) while a binary search is O(log n).

Collapse
pichardoj profile image
J. Pichardo

Nice implementation, and thanks for the book recommendation, I just have one question, how would you implement that with objects?

Collapse
stephjs profile image
Steph Author

Do you mean how would you pass in an array of objects? I modified the function a bit here to allow you to input a sorted array of objects, the key you are targeting, and the value you are searching for. (This assumes that the array is already sorted by the specific key you're looking at).

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

var sortedORainbowObj = [
  {
    id: 5,
    color: "blue"
  },
  {
    id: 4,
    color: "green"
  },
  {
    id: 6,
    color: "indigo"
  },
  {
    id: 2,
    color: "orange"
  },
  {
    id: 1,
    color: "red"
  },
  {
    id: 7,
    color: "violet"
  },
  {
    id: 3,
    color: "yellow"
  }
];

console.log(binarySearch(sortedORainbowObj, "color", "yellow")); // returns 6
console.log(binarySearch(sortedORainbowObj, "color", "maroon")); // returns null

Collapse
isaacleimgruber profile image
IsaacLeimgruber

The clean way to extend function to generic types is to override a compare function I'd say

Thread Thread
pichardoj profile image
J. Pichardo

I fully agree, nonetheless that would require using typescript, I had thought about making use of the valueOf function, however I like the way @stepho did it since it is easier to reuse, even more for js newcomers.

Collapse
pichardoj profile image
J. Pichardo

Nice function, I'm looking forward to your next post.

Collapse
kylegalbraith profile image
Kyle Galbraith

Nice write up Stephanie, clear, concise, and a great step by step guide.

Collapse
stephjs profile image
Steph Author

Thanks, Kyle!

Collapse
catcarbn profile image
Cat Carbonell

This is amazing and easy to understand! Thank you so much for this!

Collapse
svasylenko profile image
Serhii Vasylenko

Excuse me for a dumb question, I am very very new to JS but does it mean that comparison is performed not against the number of letters in a word but for the word content, so word “aaa” would be “smaller” than “aab”?

I’m referring to this:

——-
if the current element is less than (alphabetically before) the element you're searching for, increase the lowIndex to one more than the midIndex

Collapse
stephjs profile image
Steph Author

Hey Serge, no worries at all! Yes, "aaa" would be before "aab" in an alphabetical sort. The length of the word doesn't necessarily matter unless you are comparing something like "aaa" vs "aa", where "aa" would come before "aaa". A real life example of an alphabetical sort would be words in a dictionary or names in a phonebook. Feel free to copy and modify the code below and play with it in something like jsbin.com (use just the javascript and console tools).

var arr = ["aaa", "aza", "aab", "aa", "ab"];
arr.sort(); //returns ["aa", "aaa", "aab", "ab", "aza"]
Collapse
acoh3n profile image
Arik

Neat and lucid explanation. Thanks for taking the time to do that. I read grokking algorithms and loved it as well. But it's always nice to get a refresher.

Collapse
xavixo profile image
Javier Calderon

great post I learned a lot from it which helped me solved a problem i was stuck on, just hate the elToFind parameter lol

Collapse
johand profile image
Johan

Nice post, thank you.

In case anyone is interested here is the code of this book made by its author in several languages

Collapse
krishnakakade profile image
krishna kakade

Thank you for this helped me btw i follow everywhere means on internet Social Btw Merry christmas