Binary Search in Javascript

On March 1, 2014, in Javascript, by Anuj Gakhar

Binary Search is one of the fundamental algorithms in computer science. It is used to quickly find a value is a sorted set of data. It is also referred to as half-interval search, sometimes, purely because on each successive iteration, it halves the number of items to check. Binary search works by comparing an input value to the middle element of the array. When the element being compared to equals the input the search stops and returns the position of the element. If the element is not equal to the input then a comparison is made to determine whether the input is less than or greater than the element. Depending on which it is the algorithm then starts over but only searching the top or bottom subset of the array’s elements. If the input is not located within the array the algorithm will usually output a unique value indicating this.

The running time of Binary Search is O(log n) (more info on Big O notations can be found here). This is a mathematical notation which is used to classify an algorithms’ running/execution time in the worst case scenario. In simple words, O(log n) means, if there were n number of elements in the array, the algorithm would take log n with base 2 passes at the array. To give you an example, log base 2 of 100,000 is 16 and log base 2 of 1 million is 20. So, an array with a million entries in it, would only be searched for 20 times to find the input value, which is a massive improvement over Javascript’s inbuilt indexOf function which has got a running time of O(n) which means it has to go through every element in the array to find out if it’s an exact match or not.

The only thing to keep in mind is that the array must be sorted before you run Binary search on it. The code for this is actually not very hard at all. In it’s simplest form, the code could look like this :-

	function binarySearch(array, key) {
		var lo = 0,
			hi = array.length - 1,
			mid,
			element;
		while (lo <= hi) {
			mid = Math.floor((lo + hi) / 2, 10);
			element = array[mid];
			if (element < key) {
				lo = mid + 1;
			} else if (element > key) {
				hi = mid - 1;
			} else {
				return mid;
			}
		}
		return -1;
	}

We could swap out the Math.floor with Right shift bitwise operator and gain some performance improvement. There is a jsPerf that demonstrates this (note, this is not my my jsPerf). Here is the new code :-

	function binarySearch(array, key) {
		var lo = 0,
			hi = array.length - 1,
			mid,
			element;
		while (lo <= hi) {
			mid = ((lo + hi) >> 1);
			element = array[mid];
			if (element < key) {
				lo = mid + 1;
			} else if (element > key) {
				hi = mid - 1;
			} else {
				return mid;
			}
		}
		return -1;
	}

A Binary search function is available in most languages and libraries. Google’s Closure library has a binarySearch function as well. Here is a really good explanation of the algorithm in general.

 

3 Responses to Binary Search in Javascript

  1. Paul Rowe says:

    For a moment, there, I thought you were going to include the binary-sort algorithm, too, so you could make sure your array was sorted before you started searching through it.

  2. NJ IT services company Corporate core Solutions offers full IT support, it consulting, computer service, data recovery, web development.
    it consultancy

  3. Amgad Fahmi says:

    I did implement the algorithm on github with a comparison between linear and binary. let me know what do you think http://bit.ly/jsbinarysearch

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 446 other subscribers

© 2011 Anuj Gakhar
%d bloggers like this: