DEV Community

Linear and Binary Search in JavaScript

Steph on May 16, 2018

This week I started reading Grokking's Algorithms, an illustrated guide for programmers and other curious people. So far it's a fantastic read -- f...

Read full post

Hafidz Jazuli Luthfi • May 17 '18

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.

Steph • May 17 '18

Hey Hafidz,

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

Hafidz Jazuli Luthfi • May 17 '18 • Edited

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.

chowderhead • May 18 '18

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

Phil • May 20 '18

FYI ruby has already a built in binary search.

Deni • May 30 '18

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.

Steph • May 31 '18

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

J. Pichardo • May 17 '18

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

Steph • May 17 '18

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

IsaacLeimgruber • May 18 '18

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

J. Pichardo • May 19 '18 • Edited

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.

J. Pichardo • May 17 '18

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

Kyle Galbraith • May 17 '18

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

Steph • May 17 '18

Thanks, Kyle!

Cat • May 17 '18

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

Serhii Vasylenko • May 30 '18

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

Steph • May 31 '18

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"]

Arik • Jun 3 '18

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.