7 files changed, 194 insertions, 0 deletions
diff --git a/binary-search/.gitignore b/binary-search/.gitignore
new file mode 100644
index 0000000..07e6e47
--- /dev/null
+++ b/binary-search/.gitignore
@@ -0,0 +1 @@
+/node_modules
diff --git a/binary-search/.travis.yml b/binary-search/.travis.yml
new file mode 100644
index 0000000..795ac70
--- /dev/null
+++ b/binary-search/.travis.yml
@@ -0,0 +1,6 @@
+language: node_js
+node_js:
+  - '6'
+cache:
+  directories:
+    - node_modules
diff --git a/binary-search/README.md b/binary-search/README.md
new file mode 100644
index 0000000..e02805a
--- /dev/null
+++ b/binary-search/README.md
@@ -0,0 +1,46 @@
+binary-search
+=============
+
+This is a really tiny, stupid, simple binary search library for Node.JS. We
+wrote it because existing solutions were bloated and incorrect.
+
+This version is a straight port of the Java version mentioned by Joshua Bloch
+in his article, [Nearly All Binary Searches and Merge Sorts are Broken](http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html).
+
+Thanks to [Conrad Irwin](https://github.com/ConradIrwin) and [Michael
+Marino](https://github.com/mgmarino) for, ironically, pointing out bugs.
+
+Example
+-------
+
+```js
+var bs = require("binary-search");
+
+bs([1, 2, 3, 4], 3, function(element, needle) { return element - needle; });
+// => 2
+
+bs([1, 2, 4, 5], 3, function(element, needle) { return element - needle; });
+// => -3
+```
+
+Be advised that passing in a comparator function is *required*. Since you're
+probably using one for your sort function anyway, this isn't a big deal.
+
+The comparator takes a 1st and 2nd argument of element and needle, respectively.
+
+The comparator also takes a 3rd and 4th argument, the current index and array,
+respectively. You shouldn't normally need the index or array to compare values,
+but it's there if you do.
+
+You may also, optionally, specify an input range as the final two parameters,
+in case you want to limit the search to a particular range of inputs. However,
+be advised that this is generally a bad idea (but sometimes bad ideas are
+necessary).
+
+License
+-------
+
+To the extent possible by law, The Dark Sky Company, LLC has [waived all
+copyright and related or neighboring rights][cc0] to this library.
+
+[cc0]: http://creativecommons.org/publicdomain/zero/1.0/
diff --git a/binary-search/binary-search.d.ts b/binary-search/binary-search.d.ts
new file mode 100644
index 0000000..0395d93
--- /dev/null
+++ b/binary-search/binary-search.d.ts
@@ -0,0 +1,22 @@
+//Typescript type definition for:
+//https://github.com/darkskyapp/binary-search
+declare module 'binary-search' {
+
+function binarySearch<A, B>(
+  haystack: ArrayLike<A>,
+  needle: B,
+  comparator: (a: A, b: B, index?: number, haystack?: A[]) => any,
+  // Notes about comparator return value:
+  // * when a<b the comparator's returned value should be:
+  //   * negative number or a value such that `+value` is a negative number
+  //   * examples: `-1` or the string `"-1"`
+  // * when a>b the comparator's returned value should be:
+  //   * positive number or a value such that `+value` is a positive number
+  //   * examples: `1` or the string `"1"`
+  // * when a===b
+  //    * any value other than the return cases for a<b and a>b
+  //    * examples: undefined, NaN, 'abc'
+  low?: number,
+  high?: number): number; //returns index of found result or number < 0 if not found
+export = binarySearch;
+}
diff --git a/binary-search/index.js b/binary-search/index.js
new file mode 100644
index 0000000..bc281ca
--- /dev/null
+++ b/binary-search/index.js
@@ -0,0 +1,45 @@
+module.exports = function(haystack, needle, comparator, low, high) {
+  var mid, cmp;
+
+  if(low === undefined)
+    low = 0;
+
+  else {
+    low = low|0;
+    if(low < 0 || low >= haystack.length)
+      throw new RangeError("invalid lower bound");
+  }
+
+  if(high === undefined)
+    high = haystack.length - 1;
+
+  else {
+    high = high|0;
+    if(high < low || high >= haystack.length)
+      throw new RangeError("invalid upper bound");
+  }
+
+  while(low <= high) {
+    // The naive `low + high >>> 1` could fail for array lengths > 2**31
+    // because `>>>` converts its operands to int32. `low + (high - low >>> 1)`
+    // works for array lengths <= 2**32-1 which is also Javascript's max array
+    // length.
+    mid = low + ((high - low) >>> 1);
+    cmp = +comparator(haystack[mid], needle, mid, haystack);
+
+    // Too low.
+    if(cmp < 0.0)
+      low  = mid + 1;
+
+    // Too high.
+    else if(cmp > 0.0)
+      high = mid - 1;
+
+    // Key found.
+    else
+      return mid;
+  }
+
+  // Key not found.
+  return ~low;
+}
diff --git a/binary-search/package.json b/binary-search/package.json
new file mode 100644
index 0000000..9a91ed5
--- /dev/null
+++ b/binary-search/package.json
@@ -0,0 +1,28 @@
+{
+  "name": "binary-search",
+  "version": "1.3.6",
+  "description": "tiny binary search function with comparators",
+  "license": "CC0-1.0",
+  "typings": "./binary-search.d.ts",
+  "author": {
+    "name": "The Dark Sky Company, LLC",
+    "email": "support@darkskyapp.com"
+  },
+  "contributors": [
+    {
+      "name": "Darcy Parker",
+      "web": "https://github.com/darcyparker"
+    }
+  ],
+  "repository": {
+    "type": "git",
+    "url": "git://github.com/darkskyapp/binary-search.git"
+  },
+  "devDependencies": {
+    "chai": "^4.2.0",
+    "mocha": "^5.2.0"
+  },
+  "scripts": {
+    "test": "mocha"
+  }
+}
diff --git a/binary-search/test.js b/binary-search/test.js
new file mode 100644
index 0000000..95a497f
--- /dev/null
+++ b/binary-search/test.js
@@ -0,0 +1,46 @@
+var expect = require("chai").expect;
+
+describe("binarysearch", function() {
+  var bs  = require("./"),
+      arr = [1, 2, 2, 2, 3, 5, 9],
+      cmp = function(a, b) { return a - b; };
+
+  it("should bail if not passed an array", function() {
+    expect(function() { bs(undefined, 3, cmp); }).to.throw(TypeError);
+  });
+
+  it("should bail if not passed a comparator", function() {
+    expect(function() { bs(arr, 3, undefined); }).to.throw(TypeError);
+  });
+
+  it("should return the index of an item in a sorted array", function() {
+    expect(bs(arr, 3, cmp)).to.equal(4);
+  });
+
+  it("should return the index of where the item would go plus one, negated, if the item is not found", function() {
+    expect(bs(arr, 4, cmp)).to.equal(-6);
+  });
+
+  it("should return any valid index if an item exists multiple times in the array", function() {
+    expect(bs(arr, 2, cmp)).to.equal(3);
+  });
+
+  it("should work even on empty arrays", function() {
+    expect(bs([], 42, cmp)).to.equal(-1);
+  });
+
+  it("should work even on arrays of doubles", function() {
+    expect(bs([0.0, 0.1, 0.2, 0.3, 0.4], 0.25, cmp)).to.equal(-4);
+  });
+
+  it("should pass the index and array parameters to the comparator", function() {
+    var indexes = [],
+        indexCmp = function(a, b, i, array) {
+          expect(array).to.equal(arr);
+          indexes.push(i);
+          return cmp(a, b);
+        };
+    bs(arr, 3, indexCmp);
+    expect(indexes).to.deep.equal([3, 5, 4])
+  });
+});