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;
}