LeetCode problem #34 — Find First and Last Position of Element in Sorted Array (JavaScript)

In this LeetCode problem, we’re given an array of ascending numbers, and a target number, and asked to find both the first and last index of the target number in the array. In other words, given the array [1, 2, 3, 4, 5] and a target of 3, we would return [2, 2]. However given the array [1, 2, 3, 3, 3, 4, 5] and a target of 3, we would return [2, 4]. Finally, if the number cannot be found, we must return [-1, -1].

Solution #1: Binary search

Oftentimes the trick to finding anything in an ordered array quickly is to use a binary search. But what makes this problem a little different is that we aren’t just looking for the first occurrence of the target, but also the last. What this means is that we need to use two binary searches; one biased to the left, and one biased to the right.

Note #1: It is possible to simplify this code by adding a parameter such as “biasDirection” to a binary search function, and then calling the same function to find each side, but as that damages readability I’ve gone with the more drawn-out approach.

Note #2: This approach could be altered to use a binary search to find the left-hand side, and then a for loop from that point to find the right hand side. I would argue that said approach would more readable, but it would be less efficient, so I won’t include it here.

Solution #2: For loop

Predictably there is a brute force option available to use. It requires only a single pass over the data, but is slower than the aforementioned binary search approach.

Solution #3: indexOf()

Once again making use of JavaScript’s powerful indexOf() method, we can quickly ascertain the first occurrence of the target number, and then use a simple for loop from that point to find the last occurrence. Once again this solution is a little bit of a cheat, and once again it is slower than the binary search approach.