LeetCode Meditations: Search in Rotated Sorted Array
Tags: computerscience, algorithms, typescript, javascript
Published: 2024-03-28 23:49:20

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:

```ts
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](https://rivea0.github.io/blog/leetcode-meditations-find-minimum-in-rotated-sorted-array), 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 `0`th 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.

| Note |
| :-- |
| _Searching the right_ refers to updating `low` to be `mid + 1`, and _searching the left_ refers to updating `high` to be `mid - 1`. |

Here is a solution in TypeScript:

```ts
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 {% katex inline %} O(log \ n) {% endkatex %} as we use binary search, halving the search space with each iteration. The space complexity is {% katex inline %} O(1) {% endkatex %} 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.