LeetCode Meditations: Search in Rotated Sorted Array

The description for this problem states:

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

For example:

search([4, 5, 6, 7, 0, 1, 2], 0);
// -> 4


search([4, 5, 6, 7, 0, 1, 2], 3);
// -> -1


search([1], 0);
// -> -1

This one is really a hard problem where we have to think of all the cases that can possibly occur.
We'll use binary search, and similar to the previous problem, we'll consider two sorted portions in the array: left and right. Also, as with binary search, we'll have two pointers low and high pointing to the 0th and the last index respectively.
With normal binary search, we search the right portion only when the middle element is less than the target; and search the left portion when the middle element is more than the target. But here, things are different.

If we're in a sorted portion, we'll search the right if:

• the target is greater than the middle element

or

• the target is less than the value that low points to.

Otherwise, we'll go left.

Else if we're not in a sorted portion, we'll search the left if:

• the target is less than the middle element

or

• the target is greater than the value that high points to.

Otherwise, we'll go right.

Here is a solution in TypeScript:

function search(nums: number[], target: number): number {
  let low = 0;
  let high = nums.length - 1;

  while (high >= low) {
    let mid = Math.floor((high + low) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    if (nums[low] <= nums[mid]) {
      if (target > nums[mid] || target < nums[low]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    } else {
      if (target < nums[mid] || target > nums[high]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
  }

  return -1;
};

It might look confusing and hard to wrap your mind around at first, because it is. I find this problem to be one of the most challenging ones in this series so far. It means that it's now time to take a deep breath.

Time and space complexity

The time complexity is $O(log \ n)$ as we use binary search, halving the search space with each iteration. The space complexity is $O(1)$ because we don't make use of any extra space that proportionally grows with the input size.

Next up, we'll start a chapter on Linked Lists. Until then, happy coding.