Skip to content

Instantly share code, notes, and snippets.

@liesislukas
Last active April 6, 2016 11:11
Show Gist options
  • Save liesislukas/65321b3412c15695f33fd328394b198d to your computer and use it in GitHub Desktop.
Save liesislukas/65321b3412c15695f33fd328394b198d to your computer and use it in GitHub Desktop.
let list = [2,5,78,3,32,1.5,5,7,542,43,5,7,4,12,1,2,5,78,34,78,486,76845,834,15,7,5,6,8,4,6,4,8,62,768,7,3,65,4,78,51,26,68,45,2,1,5,9,3,212,56,5412,2565,47,8,652,56585,4,15,84,1,22,3,66,54,112,65654,421,2655,4,86,21564564,54444,51,1,5,12,5,8,67,86,46,87,64,8,78,786,3513,786,384,76,345,3,48,4,53,151,384,45,32,5,7,542,43,5,7,4,12,1];
let binaryFind = (haystack, needle) => {
let hi = haystack.length -1;
let lo = 0;
let mid;
let cycles = 0;
while(lo <= hi){
cycles++;
mid = Math.round((hi+lo) / 2);
if(needle > haystack[mid]){
lo = mid + 1;
} else if (needle < haystack[mid]){
hi = mid - 1;
} else {
return {index: mid, cycles: cycles};
}
}
return {index: -1, cycles: cycles};
}
list.sort((a,b) => a - b);
console.log(list);
let item = 5;
let result = binaryFind(list, item);
console.log(`item ${item} is at index ${result.index} cycles: ${result.cycles}`);
item = 87;
result = binaryFind(list, item);
console.log(`item ${item} is at index ${result.index} cycles: ${result.cycles}`);
item = 1;
result = binaryFind(list, item);
console.log(`item ${item} is at index ${result.index} cycles: ${result.cycles}`);
item = 1.5;
result = binaryFind(list, item);
console.log(`item ${item} is at index ${result.index} cycles: ${result.cycles}`);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment