# Search in Rotated Sorted Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/search-in-rotated-sorted-array)
Canonical: https://scaleengineer.com/dsa/problems/search-in-rotated-sorted-array
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Accolite](https://scaleengineer.com/companies/accolite), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Criteo](https://scaleengineer.com/companies/criteo), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Infosys](https://scaleengineer.com/companies/infosys), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Uber](https://scaleengineer.com/companies/uber), [VMware](https://scaleengineer.com/companies/vmware), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [ZScaler](https://scaleengineer.com/companies/zscaler), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [Netflix](https://scaleengineer.com/companies/netflix), [PornHub](https://scaleengineer.com/companies/pornhub), [Salesforce](https://scaleengineer.com/companies/salesforce), [Autodesk](https://scaleengineer.com/companies/autodesk), [Disney](https://scaleengineer.com/companies/disney), [Media.net](https://scaleengineer.com/companies/media.net), [Zepto](https://scaleengineer.com/companies/zepto), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Anduril](https://scaleengineer.com/companies/anduril), [Grammarly](https://scaleengineer.com/companies/grammarly), [MongoDB](https://scaleengineer.com/companies/mongodb), [Arcesium](https://scaleengineer.com/companies/arcesium), [DP world](https://scaleengineer.com/companies/dp-world), [Druva](https://scaleengineer.com/companies/druva), [Navi](https://scaleengineer.com/companies/navi), [Urban Company](https://scaleengineer.com/companies/urban-company)
---
## Problem
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`
* `-104 <= nums[i] <= 104`
* All values of `nums` are **unique**.
* `nums` is an ascending array that is possibly rotated.
* `-104 <= target <= 104`

# Approaches
## Linear Search (Brute Force)
The most straightforward approach is to perform a linear scan of the array. We can iterate through each element from the beginning to the end and check if it matches the target value. If a match is found, we return its index. If we traverse the entire array without finding the target, we return -1.
**Time:** O(n) · **Space:** O(1)
**Pros:** Very simple to understand and implement.; Works correctly for any array, regardless of its properties.
**Cons:** Inefficient for large arrays as it may require scanning the entire array.; Does not meet the O(log n) time complexity requirement specified in the problem description.
### Explanation
This brute-force method ignores the special properties of the rotated sorted array and treats it like any other unsorted list. It's simple to implement but fails to meet the performance requirements for larger datasets.

```java
class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}
```
### Algorithm
- Initialize a loop counter `i` to 0.
- Iterate through the `nums` array from `i = 0` to `nums.length - 1`.
- In each iteration, check if the current element `nums[i]` is equal to the `target`.
- If they are equal, the target is found. Return the current index `i`.
- If the loop completes without finding the target, it means the target is not in the array. Return -1.

## One-Pass Modified Binary Search
To achieve the required O(log n) time complexity, we must use a binary search. However, a standard binary search won't work because the array isn't fully sorted. The key observation is that in a rotated sorted array, when you split it at a middle point `mid`, at least one of the two halves (from `left` to `mid` or from `mid` to `right`) will always be sorted. We can use this property to our advantage. In each step of the binary search, we identify the sorted half and check if the target lies within its range. If it does, we search within that half; otherwise, we search in the other (potentially unsorted) half. This allows us to discard half of the elements in each iteration, maintaining the O(log n) complexity.
**Time:** O(log n) · **Space:** O(1)
**Pros:** Achieves the optimal O(log n) time complexity required by the problem.; Highly efficient for large input arrays.; Solves the problem in a single pass through the binary search loop.
**Cons:** The logic is more complex to understand and implement correctly compared to a standard binary search or a linear scan.
### Explanation
This approach adapts the classic binary search algorithm. At each step, we find the middle element. Then, we check if the subarray from `left` to `mid` is sorted. If it is, we can easily determine if the `target` is in this sorted subarray. If the `target` is in this range, we continue our search in the left half. Otherwise, we search in the right half. If the left subarray is not sorted, it implies the right subarray (from `mid` to `right`) must be sorted. We then apply the same logic to the right subarray. This process is repeated until the target is found or the search space is exhausted.

```java
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

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

            // Check if the left half (from left to mid) is sorted
            if (nums[left] <= nums[mid]) {
                // Check if the target is within the sorted left half
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1; // Search in the left half
                } else {
                    left = mid + 1; // Search in the right half
                }
            } 
            // Otherwise, the right half (from mid to right) must be sorted
            else {
                // Check if the target is within the sorted right half
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1; // Search in the right half
                } else {
                    right = mid - 1; // Search in the left half
                }
            }
        }

        return -1; // Target not found
    }
}
```
### Algorithm
- Initialize two pointers, `left = 0` and `right = nums.length - 1`.
- Loop as long as `left <= right`.
- Calculate the middle index: `mid = left + (right - left) / 2`.
- If `nums[mid]` is the `target`, return `mid`.
- Determine which half of the array is sorted. The key insight is that at least one half (from `left` to `mid` or `mid` to `right`) must be sorted.
- **Case 1: The left half (`nums[left]` to `nums[mid]`) is sorted.** This is true if `nums[left] <= nums[mid]`.
  - Check if the `target` lies within the range of this sorted half (`target >= nums[left]` and `target < nums[mid]`).
  - If yes, the target must be in the left half, so update `right = mid - 1`.
  - If no, the target must be in the unsorted right half, so update `left = mid + 1`.
- **Case 2: The right half (`nums[mid]` to `nums[right]`) is sorted.** This is true if `nums[left] > nums[mid]`.
  - Check if the `target` lies within the range of this sorted half (`target > nums[mid]` and `target <= nums[right]`).
  - If yes, the target must be in the right half, so update `left = mid + 1`.
  - If no, the target must be in the unsorted left half, so update `right = mid - 1`.
- If the loop finishes, the `target` was not found, so return -1.

# Solutions
### CSharp

```csharp
public class Solution {
    public int Search(int[] nums, int target) {
        int n = nums.Length;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target <= nums[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }
        return nums[left] == target ? left : -1;
    }
}
```

### Java

```java
class Solution {
public
  int search(int[] nums, int target) {
    int n = nums.length;
    int left = 0, right = n - 1;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[0] <= nums[mid]) {
        if (nums[0] <= target && target <= nums[mid]) {
          right = mid;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[n - 1]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
    }
    return nums[left] == target ? left : -1;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} target * @return {number} */ var search =
  function (nums, target) {
    const n = nums.length;
    let left = 0,
      right = n - 1;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (nums[0] <= nums[mid]) {
        if (nums[0] <= target && target <= nums[mid]) {
          right = mid;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[n - 1]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
    }
    return nums[left] == target ? left : -1;
  };

```

### CPP

```cpp
class Solution {
public:
  int search(vector<int> &nums, int target) {
    int n = nums.size();
    int left = 0, right = n - 1;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[0] <= nums[mid]) {
        if (nums[0] <= target && target <= nums[mid])
          right = mid;
        else
          left = mid + 1;
      } else {
        if (nums[mid] < target && target <= nums[n - 1])
          left = mid + 1;
        else
          right = mid;
      }
    }
    return nums[left] == target ? left : -1;
  }
};

```

### Python

```python
# below 2 solutions, diff is while condition: left ('<' or '<=') right # I like this better class Solution : def search ( self , nums : List [ int ], target : int ) -> int : n = len ( nums ) left , right = 0 , n - 1 while left <= right : mid = ( left + right ) >> 1 if nums [ mid ] == target : return mid elif nums [ 0 ] <= nums [ mid ]: # left half sorted if nums [ 0 ] <= target <= nums [ mid ]: right = mid - 1 else : left = mid + 1 else : # right half sorted if nums [ mid ] < target <= nums [ n - 1 ]: left = mid + 1 else : right = mid - 1 return - 1 ############ class Solution : def search ( self , nums : List [ int ], target : int ) -> int : n = len ( nums ) left , right = 0 , n - 1 while left < right : mid = ( left + right ) >> 1 if nums [ 0 ] <= nums [ mid ]: # left half sorted if nums [ 0 ] <= target <= nums [ mid ]: right = mid else : left = mid + 1 else : # right half sorted if nums [ mid ] < target <= nums [ n - 1 ]: left = mid + 1 else : right = mid return left if nums [ left ] == target else - 1
```