Here’s how you can find a duplicate integer in a list of integers (read array) in space O(n) and time O(nlogn). This will only return the first duplicate integer in the array. Note: This only applies for a list of integers 1..n. This won’t work otherwise. function findDuplicate(arr) { var floor = 1; var ceiling = arr.length - 1; while (floor < ceiling) { var midpoint = Math.floor(floor + (ceiling - floor) / 2); var lowerRangeFloor = floor; var lowerRangeCeiling = midpoint; var upperRangeF...
