Binary search vs linear search using JavaScript 

Binary vs linear javascript comparison

Was reading recently about the different famous algorithms and was wondering what is the difference in performance between binary and linear search as the recent known by it speed for small number of items and for unsorted data.

So I implemented binary search algorithm in JavaScript (project in github) and used performance object to measure the elapsed time for x amount of objects and compare it to normal for loop for each item.

Who is faster

binary search vs linear search

For small amount if items in the array (less than 5000) linear was faster taking in consideration the object we are looking for is the last item in the array, but over than that binary was kicking linear ass in the execution time.

Where can I see the result

I have created a test page which let you control how you want to build the comparison between the 2 algorithms, this page will let you control the number of items inside the array and what type of data it contains (number , string , objects). The page uses a  jQuery chart in order to visualize the different execution time. You can access it here.

How I have done it

how

Honestly I wasn’t planning to do all this, but this how its started.

Got curious =>  write small test => visualize it to make it more clear => expand it to perform against objects ==> clean the code and make library to be reusable => upload it to let someone else use it (sharing is caring 🙂 ) => adding sorting functionality as data might be not sorted => publish it to bower => publish it to npm => make unit testing => integrate with Travis CI => integrate with Coveralls => documentation page on Github => this article 🙂

Why you should do it

I don’t mean you implement exactly the same, my point is whenever you get a  chance to do something similar, just do it. Even its so small because you will get tons of knowledge and experience out of it. Am not an open source guy (Trying to be ) but here is some of things I get to learn while 3 days of implementations (few hours)

grunt npm node jasmine karma github travis coveralls markdown

  • Getting more experience how NPM works and knowing how to publish a package
  • Getting more experience how bower works and knowing how to publish a package
  • Getting to know more about Object Oriented in JavaScript
  • Getting to know more about continues integration systems (Travis CI)
  • Getting to know more about Task runners (grunt + karma ) and unit testing using Jasmine
  • Getting to know more about NPM packages which integrate either with grunt tasks or Karma or any other action you want to take will build process is taking place.
  • Getting to know more about markdown as I used it to document the project
  • And most important getting more excited to do more projects or at least contribute to something awesome out there.

Usage

You can install the package using NPM

npm install --save-dev js-binarysearch

Install the package using bower

bower install --save js-binarysearch

Conclusion

Your opinion is important to me, if you got the chance to use the library let me know how is it. If you got any issue with it please submit an issue to Github here.

If you have a similar story, please let’s hear it in the comments to motivate others to take the same path.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s