I answered that you could use binary search to find one of the elements. To which he replied that the element might not be the first. He then proceeded to ask me to first code binary search and then come back to the problem. This took me the rest of the interview, but I just kept sensing that he was dissatisfied by the time it was taking me. His final comment was "You got the gist of it. A few more changes to your base case and you are done." which gave the impression that I had done ok.