Binary Search

ajmataj commented 5 years ago

A demonstration of the binary search using a series of values in an array. Each comparison will be visualized and tallied. For example, an arrow could be above the value currently being checked and once the searched value is found, a tally of the total comparisons will be displayed.

brendanpettis commented 5 years ago

That'd be sweet!

ajmataj commented 5 years ago

HTML:

<!DOCTYPE html>

Binary Search

Index:
Comparisons:
Order:

ajmataj commented 5 years ago

CSS

body { font-family: 'Open Sans',sans-serif; font-size: 25px; }

h2 { font-size: 40px; }

button { height: 30px; font-size: 20px; cursor: pointer; background-color: lightgreen; color: white; border: none; font-weight: bold; }

input[type=number] { height: 30px; width: 120px; font-size: 18px; text-align: center; margin: 10px; }

input[type=number]::-webkit-inner-spin-button, input[type=number]::-webkit-outer-spin-button { -webkit-appearance: none; margin: 0; }

.highlight { background:red; color: white; }

ajmataj commented 5 years ago

JS

// Array that stores values to search from var array = [19,58,100,77,88,65,28,98,69,38,82,85,87,46,54,48,37,34,11,96];

// Sorts and displays the array function displayArray () { var numbers = ""; array.sort(function(a, b){return a-b}); for (var i = 0; i < array.length; i++) { numbers += array[i] + " "; }

document.getElementById("array").innerHTML = numbers;

}

displayArray();

// Eliminates half of the sample size with each comparison until search value is found function searchArray () { $("p").removeHighlight(); var x = document.getElementById("myNumber").value; var index = -1; var start = 0; var end = array.length-1; var valueFound = false; var comparisons = 0; var log = ""; while ((!valueFound) && (start <= end)) { comparisons++; var mid = Math.floor((start + end)/2); log += array[mid].toString() + " "; if (array[mid] == x) {valueFound = true; index = mid;} else if (array[mid] < x) {start = mid + 1;} else {end = mid - 1;} }

if (index == -1) {document.getElementById("index").innerHTML = "Value not found";}
else {document.getElementById("index").innerHTML = index; $("p").highlight(array[index].toString(), false);}
document.getElementById("tally").innerHTML = comparisons;
document.getElementById("log").innerHTML = log;

}

// From this point down is pasted code for highlight functionality jQuery.fn.highlight = function(searchString, lenient) { var input = ""; if (lenient) { input = createAccentRegexp(searchString); } else { input = searchString.toUpperCase(); } return this.each(function() { setHighlight(this, input); });

function setHighlight(node, pattern) {
  var skip = 0;
  // Do this only for text nodes. Else go find child nodes...
  if (node.nodeType == 3) {
    var index = 0;
    // If lenient then the pattern is expected to be a regexp.
    if (lenient) {
      index = node.data.search(pattern);
    } else {
      index = node.data.toUpperCase().indexOf(pattern);
    }
    if (index >= 0) {
      var spanNode = document.createElement("span");
      spanNode.className = "highlight";
      var nodeStart = node.splitText(index);
      var nodeEnd = nodeStart.splitText(searchString.length);
      var nodeHighlight = nodeStart.cloneNode(true);
      spanNode.appendChild(nodeHighlight);
      nodeStart.parentNode.replaceChild(spanNode, nodeStart);
      skip = 1;
    }
  } else {
    if (node.nodeType == 1 && node.childNodes && !/(script|style)/i.test(node.tagName)) {
      for (var i = 0; i < node.childNodes.length; ++i) {
        i += setHighlight(node.childNodes[i], pattern);
      }
    }
  }
  return skip;
}

function createAccentRegexp(characters) {
  // Replaces all accented characters.
  var deaccentedString = deaccent(characters);
  // Escapes all regexp meta characters.
  var cleanString = deaccentedString.replace(/([|()[{.+*?^$\\])/g,"\\$1");
  var accentReplacer = function(character) {
    return charToAccentedCharClassMap[character] || character;
  };
  // Matches anything *but* a whitespace and replaces it.
  var regexp = cleanString.replace(/\S/g, accentReplacer);
  return new RegExp(regexp, "g");
}

function deaccent(accentedString) {
  var result = accentedString;
  for (var key in charToAccentedCharClassMap) {    
    result = result.replace(new RegExp(charToAccentedCharClassMap[key], "g"), key);
  }
  return result;
}

};

jQuery.fn.removeHighlight = function() { return this.find("span.highlight").each(function() { this.parentNode.firstChild.nodeName; with (this.parentNode) { replaceChild(this.firstChild, this); normalize(); } }).end(); };

brendanpettis / Algorithm-Fundamentals

Binary Search #18