algorithm-visualizer · 64json · May 22, 2016 · May 22, 2016 · May 22, 2016 · May 22, 2016
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -6,6 +6,12 @@
       "bfs": "BFS"
     }
   },
+  "search": {
+    "name": "Search",
+    "list": {
+      "binary_search": "Binary Search"
+    }
+  },
   "sorting": {
     "name": "Sorting",
     "list": {

diff --git a/algorithm/search/binary_search/desc.json b/algorithm/search/binary_search/desc.json
@@ -0,0 +1,18 @@
+{
+  "Binary Search": "Binary Search is a search algorithm that finds the position of a target value within a sorted array. It works by comparing the target value to the middle element of the array; if they are unequal, the lower or upper half of the array is eliminated depending on the result and the search is repeated in the remaining subarray until it is successful.",
+  "Applications": [
+    "Finding values in a sorted collection",
+    "Traversing binary search trees"
+  ],
+  "Complexity": {
+    "time": "worst O(log(N)), best O(1), average O(log(N))",
+    "space": "worst O(log(N)) - recursive, O(1) - iterative"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Binary_search_algorithm'>Wikipedia</a>"
+  ],
+  "files": {
+    "recursive": "Recursively searching a sorted array",
+    "iterative": "Iteratively searching a sorted array"
+  }
+}
diff --git a/algorithm/search/binary_search/iterative/code.js b/algorithm/search/binary_search/iterative/code.js
@@ -0,0 +1,44 @@
+function BinarySearch(array, element) { // array = sorted array, element = element to be found,
+
+  var minIndex = 0;
+  var maxIndex = array.length - 1;
+  var currentIndex;
+  var testElement;
+
+  while (minIndex <= maxIndex) {
+
+    middleIndex = Math.floor((minIndex + maxIndex) / 2);
+    testElement = array[middleIndex];
+
+    tracer._print('Searching at index: ' + middleIndex);
+    tracer._notify(middleIndex);
+
+    if (testElement < element) {
+
+      tracer._print('Going right.');
+      minIndex = middleIndex + 1;
+
+    } else if (testElement > element) {
+
+      tracer._print('Going left.');
+      maxIndex = middleIndex - 1;
+
+    } else {
+
+      tracer._print(element + ' is found at position ' + middleIndex + '!');
+      tracer._select(middleIndex);
+
+      return middleIndex;
+    }
+  }
+
+  tracer._print(element + ' is not found!');
+  return -1;
+}
+
+var element = D[0];
+
+tracer._sleep(1000);
+tracer._pace(1000);
+tracer._print('Using iterative binary search to find ' + element);
+BinarySearch(D, element, 0, D.length - 1);
diff --git a/algorithm/search/binary_search/iterative/data.js b/algorithm/search/binary_search/iterative/data.js
@@ -0,0 +1,3 @@
+var tracer = new Array1DTracer();
+var D = Array1D.randomSorted(15, 0, 50);
+tracer._setData(D);
diff --git a/algorithm/search/binary_search/recursive/code.js b/algorithm/search/binary_search/recursive/code.js
@@ -0,0 +1,38 @@
+function BinarySearch(array, element, minIndex, maxIndex) { // array = sorted array, element = element to be found, minIndex = minIndex index, maxIndex = maxIndex index
+  if (minIndex > maxIndex) {
+    tracer._print(element + ' is not found!');
+    return -1;
+  }
+
+  var middleIndex = Math.floor((minIndex + maxIndex) / 2);
+  var testElement = array[middleIndex];
+
+  tracer._print('Searching at index: ' + middleIndex);
+  tracer._notify(middleIndex);
+
+  if (testElement < element) {
+    tracer._print('Going right.');
+    return BinarySearch(array, element, middleIndex + 1, maxIndex);
+  }
+
+  if (testElement > element) {
+    tracer._print('Going left.');
+    return BinarySearch(array, element, minIndex, middleIndex - 1);
+  }
+
+  if (testElement === element) {
+    tracer._print(element + ' is found at position ' + middleIndex + '!');
+    tracer._select(middleIndex);
+    return middleIndex;
+  }
+
+  tracer._print(element + ' is not found!');
+  return -1;
+}
+
+var element = D[0];
+
+tracer._sleep(1000);
+tracer._pace(1000);
+tracer._print('Using binary search to find ' + element);
+BinarySearch(D, element, 0, D.length - 1);
diff --git a/algorithm/search/binary_search/recursive/data.js b/algorithm/search/binary_search/recursive/data.js
@@ -0,0 +1,3 @@
+var tracer = new Array1DTracer();
+var D = Array1D.randomSorted(15, 0, 50);
+tracer._setData(D);
diff --git a/js/module/array1d.js b/js/module/array1d.js
@@ -6,18 +6,21 @@ Array1DTracer.prototype = Object.create(Array2DTracer.prototype);
 Array1DTracer.prototype.constructor = Array1DTracer;
 
 var Array1D = {
-    random: function (N, min, max) {
+    random: function(N, min, max) {
         return Array2D.random(1, N, min, max)[0];
+    },
+    randomSorted: function(N, min, max) {
+        return Array2D.randomSorted(1, N, min, max)[0];
     }
 };
 
 // Override
-Array1DTracer.prototype._setData = function (D) {
+Array1DTracer.prototype._setData = function(D) {
     return Array2DTracer.prototype._setData.call(this, [D]);
 };
 
 // Override
-Array1DTracer.prototype._notify = function (idx1, idx2) {
+Array1DTracer.prototype._notify = function(idx1, idx2) {
     if (idx2 === undefined) {
         Array2DTracer.prototype._notify.call(this, 0, idx1);
     } else {
@@ -26,7 +29,7 @@ Array1DTracer.prototype._notify = function (idx1, idx2) {
 };
 
 // Override
-Array1DTracer.prototype._select = function (s, e) {
+Array1DTracer.prototype._select = function(s, e) {
     if (e === undefined) {
         Array2DTracer.prototype._select.call(this, 0, s);
     } else {
@@ -35,16 +38,19 @@ Array1DTracer.prototype._select = function (s, e) {
 };
 
 // Override
-Array1DTracer.prototype._selectSet = function (indexes) {
+Array1DTracer.prototype._selectSet = function(indexes) {
     var coords = [];
-    indexes.forEach(function (index) {
-        coords.push({x: 0, y: index});
+    indexes.forEach(function(index) {
+        coords.push({
+            x: 0,
+            y: index
+        });
     });
     Array2DTracer.prototype._selectSet.call(this, coords);
 };
 
 // Override
-Array1DTracer.prototype._deselect = function (s, e) {
+Array1DTracer.prototype._deselect = function(s, e) {
     if (e === undefined) {
         Array2DTracer.prototype._deselect.call(this, 0, s);
     } else {
@@ -53,10 +59,13 @@ Array1DTracer.prototype._deselect = function (s, e) {
 };
 
 // Override
-Array1DTracer.prototype._deselectSet = function (indexes) {
+Array1DTracer.prototype._deselectSet = function(indexes) {
     var coords = [];
-    indexes.forEach(function (index) {
-        coords.push({x: 0, y: index});
+    indexes.forEach(function(index) {
+        coords.push({
+            x: 0,
+            y: index
+        });
     });
     Array2DTracer.prototype._deselectSet.call(this, coords);
 };