LeetCode problem #33 — Search in Rotated Sorted Array (JavaScript)
In this LeetCode problem, we’re given an array of numbers, and a target number, and asked to find the target number in the array (or return -1 if it cannot be found). As an added complexity, the array is in ascending order, but not from start to finish. Instead, the pivot point (the point at which the ordering “resets”) is unknown.
This complication is billed as a “rotated sorted array”, and what it basically means is that a sorted array of [1, 2, 3, 4, 5] has been “rotated” or pivoted at a random point, meaning you might be given [3, 4, 5, 1, 2] or [5, 1, 2, 3, 4].
The reason this complexity matters is that a standard binary search will no longer work, because after slicing the array in two, you cannot simply say “is the target in the left or right side” in the traditional “greater than array[left] and less than array[middle]” as you would for a normal binary search.
Solution #1: An adjusted binary search
In reality, the solution is not that different to a normal binary search; we simply have to accommodate the complexity. This is handled by adding an extra step to the aforementioned logic, which becomes “Is the left-hand side ordered? If yes, is the target greater than or equal to array[left] and less than array[middle] (AKA on the left side)? If no, is the target greater than or equal to array[middle] (AKA on the right side)?”.
This is because once you pivot or rotate an array at a single point, half of the array will still be ordered in a standard ascending fashion, meaning we can still apply the same logic to that side, and by doing so, identify which side the number belongs to.
So what exactly are we doing here? Well in simple terms, we’re repeatedly diving the array of numbers in 2, and looking at each side to see if it contains our target number. We continue this process until we find our target number, either because we find it at the middle point, or because we get down to our last available number, at which point we’ve either found the target, or can safely say that the target was not present in the array.
Solution #2: Cheat
If, like me, you saw this question and thought “isn’t that incredibly simply?”, you’d be right. A standard brute force approach would simply be to loop through all numbers in the array, looking for the target, like so:
Even better, we can use JavaScript’s built-in indexOf() method, which not only finds a value in an array, but even returns the correct response (-1) if the value can’t be found.
But both of these solutions require every value in the array to be checked, which of course makes them inefficient. By splitting our array in the earlier outlined binary search method, we reduce the number of checks required dramatically. Additionally, as we are using our own code and not built-in functionality (such as with indexOf()), we can assume that the performance of our approach will remain roughly unchanged between browsers and browser versions.
That said, I would never personally expect a developer to use a binary search over indexOf() in actual production code…