Binary Search for Javascript Arrays

If you need to search through a large array, or you search arrays frequently in your Javascript code, or if you do both, chances are a binary search will give you better performance than a linear search (read: for loop). One caveat, however, is that binary search algorithms only work on sorted arrays. Here is a binary search function I sometimes use in my code:

Array.prototype.binSearch = function(needle, case_insensitive) {
    if (!this.length) return -1;

	var high = this.length - 1;
	var low = 0;
	case_insensitive = (typeof(case_insensitive) !== 'undefined' && case_insensitive) ? true:false;
	needle = (case_insensitive) ? needle.toLowerCase():needle;

	while (low <= high) {
		mid = parseInt((low + high) / 2)
		element = (case_insensitive) ? this[mid].toLowerCase():this[mid];
		if (element > needle) {
			high = mid - 1;
		} else if (element < needle) {
			low = mid + 1;
		} else {
			return mid;
		}
	}

	return -1;
};

Related posts:

  1. Javascript For-in Loops
  2. LongURL Integration For Your Website
April 29, 2009 | Filed Under Code Snippets, Performance, Programming | Tagged , , ,  

Comments

Leave a Reply