Today, an interviewer asked me this question. My immediate response was that we could simply do a linear search, comparing the current element with the previous element in the array. He then asked me how the problem could be solved in less-than-linear time.

Assumptions

  • The array is sorted
  • There is only one duplicate
  • The array is only populated with numbers [0, n], where n is the length of the array.

Example array: [0,1,2,3,4,5,6,7,8,8,9]

I attempted to come up with a divide-and-conquer algorithm to solve this, but I'm not confident that it was the right answer. Does anyone have any ideas?

arrays algorithm search language-agnostic data-structures
Edit
Report