Search in Rotated Sorted Array

Today I came across the LeetCode problem Search in Rotated Sorted array, which asks you to find the index of a value in a rotated sorted array in O(log n) time.

Immediately I wanted to use a binary search to achieve O(log n) time as the array was already (almost) sorted. A sorted array might look like [1, 3, 7, 12, 17, 22, 29, 46, 58]. Since we are given a rotated sorted array, our input array would look something more like [29, 46, 58, 1, 3, 7, 12, 17, 22]. This is the same array, rotated to the right three spaces.

The second parameter we are given is a target value, for which we need to return the index of. For example

searchRotatedSortedArray([29, 46, 58, 1, 3, 7, 12, 17, 22], 12) //returns 6

A basic implementation of this might iterate through the input array checking each value against the target value. While this would certainly work, it’s running in linear time, meaning we need to run one operation for each element in the input array. This means that the running time for the algorithm increases linearly with the size of the input. For this problem, we are looking to optimize for a much quicker search and aim for logarithmic time complexity. This means we want to cut down the number of items we need to search through with each operation. A great example of this is binary search. In order to solve this problem with the given constraints, we will use a similar approach.

We will need to keep track of three different positions while searching the array. First we want to locate the beginning and end of the array, as well as the center point. For our example above, the array contains 8 numbers. The beginning index will always start at 0, and the end index will always start at array.length — 1 , giving us 7. We will use Math.floor to find our middle point, which in this case gives us 3, however our start and end numbers may change, so we need to always find the number in the middle of those two values.

Next we can check if our middle number is equal to our target, and if it is, were done! Although that’s likely not the case. If it’s not, we will then begin comparing values to check if either portion of our array is sorted.

Once we find the sorted portion, we can check if the target value is (or would be) in that portion of the array by comparing our target against the beginning and ending value of the array portion, and making sure it falls in between the two. Once we find which portion of our array the target is in, we can reset our left/right and mid values effectively cutting out half of the array to restart our process.