# Search in Rotated Sorted Array

- **Canonical ID**: `search-in-rotated-sorted-array`
- **Canonical URL**: https://dsacheatsheet.com/problems/search-in-rotated-sorted-array
- **Difficulty**: medium
- **Patterns**: Binary Search
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/search-in-rotated-sorted-array/

## 1. Core Invariant / The Trick

At least one half (`[l..mid]` or `[mid..r]`) is guaranteed strictly sorted. Identify the sorted half via `nums[l] <= nums[mid]`, check whether `target` falls within its numeric bounds, and discard the other half.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(log N)`
- **Space Complexity**: `O(1)`
- **Proof**: Halves search window per comparison without finding pivot in a separate pass.

## 3. Minimal Idiomatic Code

### Python
```python
def searchRotated(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1
    while l <= r:
        m = (l + r) // 2
        if nums[m] == target: return m
        if nums[l] <= nums[m]:
            if nums[l] <= target < nums[m]: r = m - 1
            else: l = m + 1
        else:
            if nums[m] < target <= nums[r]: l = m + 1
            else: r = m - 1
    return -1
```

### TypeScript
```typescript
export function searchRotated(nums: number[], target: number): number {
  let l = 0, r = nums.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (nums[m] === target) return m;
    if (nums[l] <= nums[m]) {
      if (nums[l] <= target && target < nums[m]) r = m - 1; else l = m + 1;
    } else {
      if (nums[m] < target && target <= nums[r]) l = m + 1; else r = m - 1;
    }
  }
  return -1;
}
```

### C++
```cpp
int search(vector<int>& n, int t) {
    int l = 0, r = n.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (n[m] == t) return m;
        if (n[l] <= n[m]) { (n[l] <= t && t < n[m]) ? r = m - 1 : l = m + 1; }
        else { (n[m] < t && t <= n[r]) ? l = m + 1 : r = m - 1; }
    }
    return -1;
}
```

### Java
```java
int search(int[] n, int t) {
    int l = 0, r = n.length - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (n[m] == t) return m;
        if (n[l] <= n[m]) { if (n[l] <= t && t < n[m]) r = m - 1; else l = m + 1; }
        else { if (n[m] < t && t <= n[r]) l = m + 1; else r = m - 1; }
    }
    return -1;
}
```

### Go
```go
func search(n []int, t int) int {
    l, r := 0, len(n)-1
    for l <= r {
        m := (l + r) / 2
        if n[m] == t { return m }
        if n[l] <= n[m] {
            if n[l] <= t && t < n[m] { r = m - 1 } else { l = m + 1 }
        } else {
            if n[m] < t && t <= n[r] { l = m + 1 } else { r = m - 1 }
        }
    }
    return -1
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Note `<=` in `nums[l] <= nums[mid]` when `l == mid` on a 2-element subarray.

### Follow-ups
- Rotated Array with duplicates (`Search II`): handle `nums[l] == nums[mid] == nums[r]` by `l++; r--;`.