Skip to content

Instantly share code, notes, and snippets.

@calebdwilliams
Last active March 22, 2016 20:55
Show Gist options
  • Save calebdwilliams/0693a198203395aae865 to your computer and use it in GitHub Desktop.
Save calebdwilliams/0693a198203395aae865 to your computer and use it in GitHub Desktop.
Basic binary search demonstration.
function generateArray() {
'use strict';
let length = Math.floor(Math.random() * 100000),
remove = Math.floor(Math.random() * length),
array = [];
for (let counter = 0; counter <= length; counter += 1) {
array.push(counter);
}
array.splice(remove, 1);
console.log(remove);
return array;
}
function findMissing(array) {
'use strict';
let start = 0,
finish = array.length,
pointer = Math.floor((finish - start) / 2),
result = false,
counter = 0;
while(!result) {
if (array[pointer] > pointer) {
if (array[pointer - 1] === pointer - 1) {
result = pointer;
}
finish = pointer;
pointer = Math.floor((finish - start) / 2);
if (finish === pointer) {
pointer -= 1;
}
} else if (array[pointer] === pointer) {
start = pointer;
pointer = Math.floor((finish + start) / 2);
if (finish === pointer) {
pointer += 1;
}
}
counter += 1;
if (counter > array.length) {
result = -1;
}
}
return {
result: result,
counter: counter
};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment