Append array element only if it is not already there in Javascript

I need to add an element to an array only if it is not already there in Javascript. Basically I'm treating the array as a set.

I need the data to be stored in an array, otherwise I'd just use an object which can be used as a set.

I wrote the following array prototype and wanted to hear if anyone knew of a better way. This is an O(n) insert. I was hoping to do O(ln(n)) insert, however, I didn't see an easy way to insert an element into a sorted array. For my applications, the array lengths will be very small, but I'd still prefer something that obeyed accepted rules for good algorithm efficiency:

Array.prototype.push_if_not_duplicate = function(new_element){
    for( var i=0; i<this.length; i++ ){开发者_StackOverflow社区
        // Don't add if element is already found
        if( this[i] == new_element ){
            return this.length;
        }
    }
    // add new element
    return this.push(new_element);
}

---

If I understand correctly, you already have a sorted array (if you do not have a sorted array then you can use Array.sort method to sort your data) and now you want to add an element to it if it is not already present in the array. I extracted the binary insert (which uses binary search) method in the google closure library. The relevant code itself would look something like this and it is O(log n) operation because binary search is O(log n).

function binaryInsert(array, value) {
  var index = binarySearch(array, value);
  if (index < 0) {
    array.splice(-(index + 1), 0, value);
    return true;
  }
  return false;
};

function binarySearch(arr, value) {
  var left = 0;  // inclusive
  var right = arr.length;  // exclusive
  var found;
  while (left < right) {
    var middle = (left + right) >> 1;

    var compareResult = value > arr[middle] ? 1 : value < arr[middle] ? -1 : 0;
    if (compareResult > 0) {
      left = middle + 1;
    } else {
      right = middle;
      // We are looking for the lowest index so we can't return immediately.
      found = !compareResult;
    }
  }
  // left is the index if found, or the insertion point otherwise.
  // ~left is a shorthand for -left - 1.
  return found ? left : ~left;
};

Usage is binaryInsert(array, value). This also maintains the sort of the array.

---

Deleted my other answer because I missed the fact that the array is sorted.

The algorithm you wrote goes through every element in the array and if there are no matches appends the new element on the end. I assume this means you are running another sort after.

The whole algorithm could be improved by using a divide and conquer algorithm. Choose an element in the middle of the array, compare with new element and continue until you find the spot where to insert. It will be slightly faster than your above algorithm, and won't require a sort afterwards.

If you need help working out the algorithm, feel free to ask.

---

I've created a (simple and incomplete) Set type before like this:

var Set = function (hashCodeGenerator) {
    this.hashCode = hashCodeGenerator;
    this.set = {};
    this.elements = [];
};
Set.prototype = {
  add: function (element) {
    var hashCode = this.hashCode(element);
    if (this.set[hashCode]) return false;
    this.set[hashCode] = true;
    this.elements.push(element);
    return true;
  },
  get: function (element) {
    var hashCode = this.hashCode(element);
    return this.set[hashCode];
  },
  getElements: function () { return this.elements; }
};

You just need to find out a good hashCodeGenerator function for your objects. If your objects are primitives, this function can return the object itself. You can then access the set elements in array form from the getElements accessor. Inserts are O(1). Space requirements are O(2n).

---

If your array is a binary tree, you can insert in O(log n) by putting the new element on the end and bubbling it up into place. Checks for duplicates would also take O(log n) to perform.

Wikipedia has a great explanation.