Skip to content

Instantly share code, notes, and snippets.

@pzaich

pzaich/find_dupes.js

Created August 26, 2016 05:00
Show Gist options
  • Save pzaich/c7e7c9307d9f66a14b246e7f79c67a3f to your computer and use it in GitHub Desktop.
Save pzaich/c7e7c9307d9f66a14b246e7f79c67a3f to your computer and use it in GitHub Desktop.
Download ZIP
Find duplicates in a sorted array in Olog(n)
Raw
find_dupes.js
// Find duplicate in sorted array
var sortedArray = [1,2,3,3,4,5,6,7,8];
var sortedNoDupes = [1,2,3,,4,5,6,7,8];
// Binary search
function findDuplicate(arr) {
var midpoint = Math.floor(arr.length / 2);
var mid = arr[midpoint];
var left = arr[midpoint - 1];
var right = arr[midpoint + 1];
if (mid === left || mid === right) {
return mid;
} else {
left = findDuplicate(arr.slice(0, midpoint));
right = findDuplicate(arr.slice(midpoint + 1, arr.length));
return left || right;
}
}
console.log(findDuplicate(sortedArray))
console.log(findDuplicate(sortedNoDupes))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment