JavaScript is a computer programming language that most often runs inside a web browser as part of a web page. It is a simple yet powerful interpreted language that includes several built-in classes and functions. One of these built-in classes is the Array class which has powerful functions such as concat, sort, slice, and splice. However, there are several useful functions, linearSearch, binarySearch, retainAll, and removeAll, that were not included in the Array class. This article shows you how to add these four useful functions plus two other convenience functions, addAll and contains, to the JavaScript Array class. If you put these functions in a JavaScript file named array.js, you will be able to include and use them in a web page whenever you want.
Descriptions of the Functions
The linearSearch function searches an array for an occurrence of some value called a key. It searches the array from the beginning to the end of the array, stopping when it finds the key or reaches the end of the array. If the key is stored in the array, the linearSearch function returns the index of the first occurrence of the key. Otherwise, it returns -1. linearSearch works well for arrays that are small (perhaps less than 100 elements).
If the elements in an array are sorted, then the computer can use a faster algorithm called binary search to find an element within that array. The binarySearch function works by comparing the key to the middle most element in the array. If the key is less than the middle most element, then the search is repeated in the first half of the array. If the key is greater than the middle most element, then the search is repeated in the last half of the array. Of course, if the key is equal to the middle most element, then the key has been found and the search is done. This process of comparing the key to the middle most element of the current interval is repeated until the key is found or the interval has shrunk to only 1 element. If that one element is not the same as the key, then the key is not present in the array.
The contains function is similar to linearSearch. However, the contains function returns true if the key is stored in the array and returns false otherwise. This is different from the linearSearch and binarySearch functions which both return the index where the key is stored in the array.
The addAll function is similar to the built-in concat function, but the addAll function adds elements to an existing array instead of returning a new array as the concat function does. The addAll function can be used to compute the union of arrays.
The retainAll function retains in an array all the elements that are also contained in a second array. This is similar to computing the intersection of the two arrays.
The removeAll function removes from an array all the elements that are also contained in another array. This is similar to computing the complement of the first array relative to the second.
The Six Missing Functions
Here are the six missing JavaScript Array functions. Copy these functions into a text file named array.js. Notice that all the functions except addAll have an optional parameter which is a comparison function. If your program is storing complex objects in arrays, you can write your own comparison function to compare the objects any way you like.
/** If this array contains key, returns the index of
* the first occurrence of key; otherwise returns -1. */
Array.prototype.linearSearch = function(key, compare) {
if (typeof(compare) == "undefined") {
compare = simpleCompare;
}
for (var i = 0; i < this.length; i++) {
if (compare(this[i], key) == 0) {
return i;
}
}
return -1;
}
/** If this array contains key, returns the index of
* any occurrence of key; otherwise returns -1.
* Assumes this array is already sorted. */
Array.prototype.binarySearch = function(key, compare) {
if (typeof(compare) == "undefined") {
compare = simpleCompare;
}
var left = 0;
var right = this.length - 1;
while (left <= right) {
var mid = left + Math.floor((right - left) / 2);
var cmp = compare(key, this[mid]);
if (cmp < 0)
