var haystack = []; var output = document.getElementById("output"); var amount = 100; for (var i = 1; i <= amount; i++) { //if (i % 2 == 0) haystack.push(i); haystack.push(i); } function log(message) { output.innerHTML += message + "\n"; } function arraySlice(start, end, array) { var slice = []; for (start; start < end; start++) { var value = array[start]; slice.push(value); } return slice; } function getMin(array) { var min = Infinity; for (var i = 0; i < array.length; i++) { min = ( min > array[i]) ? array[i] : min; } return min; } function getMax(array) { var max = 0; for (var i = 0; i < array.length; i++) { max = ( max < array[i]) ? array[i] : max; } return max; } var ITERATIONS = 0; function reset() { ITERATIONS = 0; } function search(needle, haystack) { ITERATIONS++; log("\n" + 'Search No. ' + ITERATIONS + "\n----"); log('index range: ' + 0 + ' - ' + haystack.length); var middle = Math.floor(haystack.length / 2); log('middle index: ' + middle); var value = haystack[middle]; log('value: ' + value); if (needle == value) { log('search succeeded to find: ' + needle + ' at index:' + middle); log(needle + ' = ' + value); reset(); } else if(needle > value) { log(needle + ' > ' + value); var start = middle + 1; var end = haystack.length; log('searching right ' + start + ' - ' + end); var difference = end - start; if (difference != 0) { var right = arraySlice(start, end, haystack); search(needle, right); } else { log('search failed to find: ' + needle + ': start index ' + start + ' = end index: ' + end); reset(); } } else if(needle < value) { log(needle + ' < ' + value); var start = 0; var end = middle; log('searching left ' + start + ' - ' + end); var difference = end - start; if (difference != 0) { var left = arraySlice(start, end, haystack); search(needle, left); } else { log('search failed to find: ' + needle + ': start index ' + start + ' = end index: ' + end); reset(); } } } function binarySearch(needle, haystack) { log("\n" + 'Checking if ' + needle + ' is in min - max range' + "\n----"); var min = getMin(haystack); var max = getMax(haystack); log('Range: ' + min + ' - ' + max); var isOutOfBounds = false; if (needle < min) { log(needle + ' < ' + min); isOutOfBounds = true; } else if(needle > max) { log(needle + ' > ' + max); isOutOfBounds = true; } if ( isOutOfBounds) log('No'); if ( ! isOutOfBounds) { log(min + ' < ' + needle + ' > ' + max); log('Yes'); search(needle, haystack); } } function formatOutput() { var regex = /(\d+)/g; output.innerHTML = output.innerHTML.replace(regex, function(match, group) { return '<span class="digit">' + match + '</span>'; }); regex = /( - )/g; output.innerHTML = output.innerHTML.replace(regex, function(match, group) { return '<span class="dash">' + match + '</span>'; }); } var input = document.getElementById('input'); input.onsubmit = function(e) { e.preventDefault(); output.innerHTML = ''; var q = document.getElementById('q'); var value = q.value; var values = value.split(','); for (var i = 0; i < values.length; i++) { var needle = parseInt(values[i]); binarySearch(needle, haystack); formatOutput(); } };
<div id="wrap"> <h1 id="title">Binary Search Example</h1> <form id="input"> <p>Input:</p> <input id="q" name="q" type="text" placeholder="Enter numbers seprated by comas"/> <button id="submit" type="submit">Search</button> </form> <p>Data</p> <p>Output:</p> <pre id="output"> </pre> </div>
html, body, form, input, button{ width: 100%; } input, button{ border: none; } button{ background: #68f; color: #fff; font-size: 16px; } input:focus{ outline: none; border: 1px solid #68f; } #title{ text-align: center; } #wrap{ padding: 2em; background: #ddd; width: 512px; } #q, #submit{ padding: 1em 0; } #q{ text-indent: 1em; } #output{ background: #fff; padding: 1em; border: 1px solid #111; } #wrap, #q, #submit, #output{ border-radius: 1em; } #output .digit{ font-size: 16px; color: #68f; } #output .operator{ font-size: 62px; color: #f00; } #output .dash{ font-size: 16px; color: #f00; }