---
description: >-
  Author: @vigneshshiv, @radojicic23 |
  https://leetcode.com/problems/search-in-rotated-sorted-array/
---

# 0033 - Search in Rotated Sorted Array (Medium)

## Problem Link

https://leetcode.com/problems/search-in-rotated-sorted-array/

## Problem Statement

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.

**Example 1:**

```
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
```

**Example 2:**

```
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
```

**Example 3:**

```
Input: nums = [1], target = 0
Output: -1
```

**Constraints:**

- `1 <= nums.length <= 5000`
- `-10^4 <= nums[i] <= 10^4`
- All values of `nums` are **unique**.
- `nums` is a non-decreasing array.
- `-10^4 <= target <= 10^4`

## Approach 1: Binary Search

:::info Prerequisite

- [Binary Search](../../tutorials/basic-topics/binary-search)

:::

As a problem stated, the array is rotated, How do we apply a binary search?

Since the array is rotated in `Example #1` assume first half from index $0-3$ is in ascending order, the second half is decending order from the first half.

With this approach we can solve the problem by finding the pivot index. Here, pivot is the maximum element in the array.

If the given target is greater than the start index element, then the element must be with in the highest element. So reduce the space of the array to $0$ to $pivot-1$, otherwise search in $pivot+1$ to $nums.length - 1$.

<Tabs>
<TabItem value="java" label="Java">
<SolutionAuthor name="@vigneshshiv"/>

```java
class Solution {
    public int search(int[] nums, int target) {
        // Base case
        if (Objects.isNull(nums) || nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int pivot = findPivot(nums);
        // If pivot not found, Do a normal binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }
        if (nums[pivot] == target) {
            return pivot;
        }
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1);
        }
        return binarySearch(nums, target, pivot + 1, nums.length - 1);
    }


    public int findPivot(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            // 1. if middle element is greater than next element, which means middle element is the highest,
            // and next element starts in ascending order
            if (mid < high && nums[mid] > nums[mid + 1]) {
                return mid;
            }
            // 2. if middle element is smaller than the previous element, which means from middle element,
            // elements are placed in ascending order, and previous element is the highest
            if (mid > low && nums[mid] < nums[mid - 1]) {
                return mid - 1;
            }
            // 3. If middle element less than the start element, the highest element or arrays are the left side
            if (nums[mid] <= nums[low]) {
                high = mid - 1;
            } else {
                // 4. Search after middle element, to find the pivot which is the highest element
                low = mid + 1;
            }
        }
        return -1;
    }

    public int binarySearch(int[] nums, int target, int low, int high) {
        int mid = 0;
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (target < nums[mid]) {
                high = mid - 1;
            } else if (target > nums[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
```

</TabItem>

<TabItem value="python" label="Python">
<SolutionAuthor name="@radojicic23"/>

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            # mid value
            mid = (l + r) // 2
            # if mid is target
            if target == nums[mid]:
                return mid

            # are we in left sorted portion or right sorted portion
            if nums[mid] >= nums[l]:
                # we are in right sorted portion in this case
                if target > nums[mid] or target < nums[l]:
                    l = mid + 1
                # we are in left sorted portion in this case
                else:
                    r = mid - 1
            else:
                # we are in left sorted portion in this case
                if target < nums[mid] or target > nums[r]:
                    r = mid - 1
                # we are in right sorted portion in this case
                else:
                    l = mid + 1

        return -1
```

</TabItem>

<TabItem value="js" label="JavaScript">
<SolutionAuthor name="@radojicic23"/>

```js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let l = 0;
  let r = nums.length - 1;
  while (l <= r) {
    //mid value
    let mid = Math.floor((l + r) / 2);
    // if mid is target -> return mid index
    if (nums[mid] == target) return mid;
    // are we in left or right sorted portion
    if (nums[mid] >= nums[l]) {
      // we are in right sorted portion
      if (target > nums[mid] || target < nums[l]) {
        l = mid + 1;
        // we are in left sorted portion
      } else {
        r = mid - 1;
      }
    } else {
      // we are in left sorted portion
      if (target < nums[mid] || target > nums[r]) {
        r = mid - 1;
        // we are in right sorted portion
      } else {
        l = mid + 1;
      }
    }
  }
  return -1;
};
```

</TabItem>

<TabItem value="cpp" label="C++">
<SolutionAuthor name="@radojicic23"/>

```cpp
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        while (l <= r) {
            // mid value
            int mid = l + (r - l) / 2;
            // if mid is target return mid index
            if (nums[mid] == target) {
                return mid;
            }
            // are we in right or left sorted portion
            if (nums[mid] >= nums[l]) {
                // we are in right sorted portion
                if (target > nums[mid] || target < nums[l]) {
                    l = mid + 1;
                // we are in left sorted portion
                } else {
                    r = mid - 1;
                }
            } else {
                // we are in left sorted portion 
                if (target < nums[mid] || target > nums[r]) {
                    r = mid - 1;
                // we are in right sorted portion
                } else {
                    l = mid + 1;
                }
            }
        }
        return -1;
    }
};
```

</TabItem>
</Tabs>
