5. Find a Single Element

Here's the problem presented by the interviewer:

Given a sorted array of integers, every element appears twice except for one. Find that single element.

Define the Problem

The problem has been explained fairly well by the interviewer, but we're going to have Jonathan clear up any doubts or assumptions.

Jonathan: I'll be using JavaScript to solve the problem.

Interviewer: Okay.

---

Think

Jonathan thinks about the problem for a bit. He's already starting to come up with some solutions and writes out some of his thoughts on the board. Here's his pseudocode:

// Sorted Array - Linear Search
// Create function that will take in an array and return the unique element
function uniqueNumSorted(arr) {
    // Loop through each element in the array and check the previous and next element to see if they are equal
    // Return element that is unequal to previous and next element.

---

Write Code and Syntax

Now that Jonathan has figured out the logic, he translates it into JavaScript.

for (var i = 0; i < arr.length; i++) {
    if (arr[i] !== arr[i + 1] && arr[i] !== arr[i - 1]) {
        return arr[i];
        }
    }
}

Jonathan: I thought about different ways of going about this, and the simplest solution seems to be using a for loop. Within the loop, I check to see if the element is not equal to the previous and next element in the array. This is only true for the element that is unique, since the elements are sorted.

Interviewer: What is the time complexity?

Jonathan: O(n), since we're just going through each element once in the for loop.