Search in Rotated Sorted Array

Problem Statement

There is an integer array nums sorted in ascending order. It is then rotated at some unknown pivot. Given the rotated array and a target value, return the index of target if it exists, otherwise return -1.

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

What to notice first

• The array is rotated, but one half is still sorted.
• Identify which half is sorted, then check if target is in that half.
• If target is in the sorted half, search that half; otherwise, search the other half.

Examples

Input	Target	Output	Explanation
[4, 5, 6, 7, 0, 1, 2]	0	4	Target found at index 4
[4, 5, 6, 7, 0, 1, 2]	3	-1	Target not in array
[1]	1	0	Single element matches target
[3, 1]	3	0	Rotated array, target at start

Constraints

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values in nums are unique
• nums is guaranteed to be rotated at some pivot
• -10^4 <= target <= 10^4

Real-World Applications

Where this pattern appears

• Cyclic buffer search — finding elements in a circular queue that has been partially rotated.
• Log file analysis — searching timestamps in rotated daily logs.
• Round-robin scheduling — finding a task in a rotated schedule.
• Database sharding — locating data in a rotated partition.

Complexity Comparison

Approach	Time	Space	Best When
Binary Search	O(log n)	O(1)	Standard approach, O(log n) required
Linear Search	O(n)	O(1)	Very small arrays, simplicity preferred

Which approach should you learn first?

• Pick Binary Search to meet the O(log n) constraint and master the pattern.
• Pick Linear Search to understand the problem conceptually first.

Required Time

Binary Search

O(log n) time · O(1) space

Simplicity

Linear Search

O(n) time · O(1) space

Approach 1: Binary Search (Recommended)

★ Recommended

Identify which half is sorted by comparing nums[left] with nums[mid]. Then determine if the target is in the sorted half or the unsorted half, and adjust the search accordingly.

⏱ Time O(log n) Halve search space each iteration 💾 Space O(1) Only pointers

Step-by-step Example

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

Step	left	right	mid	Sorted Half	nums[mid]	In Range?	Action
1	0	6	3	Left (4-7)	7	No	right = 2
2	0	2	1	Left (4-6)	5	No	right = 0
3	0	0	0	—	4	No	left = 1
4	1	0	—	—	—	—	Search right half, return 4 ✓

Pseudocode

function search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target:
            return mid

        // Determine which half is sorted
        if nums[left] <= nums[mid]:
            // Left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            // Right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Solution Code

Python

search_in_rotated_sorted_array_binary_search.py

"""
#33 Search in Rotated Sorted Array - Binary Search Approach
Time: O(log n), Space: O(1)

A rotated sorted array has been rotated at an unknown pivot.
Use binary search to find target, identifying which half is sorted.
"""


class Solution:
    def search(self, nums: list[int], target: int) -> int:
        """
        Binary search on rotated array.
        Determine which half is sorted, then check if target is in that half.
        """
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid

            # Determine which half is sorted
            if nums[left] <= nums[mid]:
                # Left half is sorted
                if nums[left] <= target < nums[mid]:
                    # Target is in sorted left half
                    right = mid - 1
                else:
                    # Target is in right half
                    left = mid + 1
            else:
                # Right half is sorted
                if nums[mid] < target <= nums[right]:
                    # Target is in sorted right half
                    left = mid + 1
                else:
                    # Target is in left half
                    right = mid - 1

        return -1


# Test cases
if __name__ == "__main__":
    sol = Solution()

    assert sol.search([4, 5, 6, 7, 0, 1, 2], 0) == 4
    assert sol.search([4, 5, 6, 7, 0, 1, 2], 3) == -1
    assert sol.search([1], 1) == 0
    assert sol.search([1, 3], 3) == 1
    assert sol.search([3, 1], 3) == 0

    print("All test cases passed!")

C++

search_in_rotated_sorted_array_binary_search.cpp

#include <vector>
using namespace std;

/*
#33 Search in Rotated Sorted Array - Binary Search Approach
Time: O(log n), Space: O(1)

A rotated sorted array has been rotated at an unknown pivot.
Use binary search to find target, identifying which half is sorted.
*/

class Solution {
public:
    int search(vector<int>& nums, int target) {
        /*
        Binary search on rotated array.
        Determine which half is sorted, then check if target is in that half.
        */
        int left = 0, right = nums.size() - 1;

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

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

            // Determine which half is sorted
            if (nums[left] <= nums[mid]) {
                // Left half is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    // Target is in sorted left half
                    right = mid - 1;
                } else {
                    // Target is in right half
                    left = mid + 1;
                }
            } else {
                // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    // Target is in sorted right half
                    left = mid + 1;
                } else {
                    // Target is in left half
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
};

Java

SearchInRotatedSortedArrayBinarySearch.java

/*
#33 Search in Rotated Sorted Array - Binary Search Approach
Time: O(log n), Space: O(1)

A rotated sorted array has been rotated at an unknown pivot.
Use binary search to find target, identifying which half is sorted.
*/

class Solution {
    public int search(int[] nums, int target) {
        /*
        Binary search on rotated array.
        Determine which half is sorted, then check if target is in that half.
        */
        int left = 0, right = nums.length - 1;

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

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

            // Determine which half is sorted
            if (nums[left] <= nums[mid]) {
                // Left half is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    // Target is in sorted left half
                    right = mid - 1;
                } else {
                    // Target is in right half
                    left = mid + 1;
                }
            } else {
                // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    // Target is in sorted right half
                    left = mid + 1;
                } else {
                    // Target is in left half
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

JavaScript

search_in_rotated_sorted_array_binary_search.js

/**
 * #33 Search in Rotated Sorted Array - Binary Search Approach
 * Time: O(log n), Space: O(1)
 *
 * A rotated sorted array has been rotated at an unknown pivot.
 * Use binary search to find target, identifying which half is sorted.
 */

class Solution {
    search(nums, target) {
        /**
         * Binary search on rotated array.
         * Determine which half is sorted, then check if target is in that half.
         */
        let left = 0, right = nums.length - 1;

        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);

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

            // Determine which half is sorted
            if (nums[left] <= nums[mid]) {
                // Left half is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    // Target is in sorted left half
                    right = mid - 1;
                } else {
                    // Target is in right half
                    left = mid + 1;
                }
            } else {
                // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    // Target is in sorted right half
                    left = mid + 1;
                } else {
                    // Target is in left half
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

// Export for CommonJS
module.exports = Solution;

Rust

search_in_rotated_sorted_array_binary_search.rs

/*
#33 Search in Rotated Sorted Array - Binary Search Approach
Time: O(log n), Space: O(1)

A rotated sorted array has been rotated at an unknown pivot.
Use binary search to find target, identifying which half is sorted.
*/

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        /*
        Binary search on rotated array.
        Determine which half is sorted, then check if target is in that half.
        */
        let mut left = 0i32;
        let mut right = nums.len() as i32 - 1;

        while left <= right {
            let mid = (left + (right - left) / 2) as usize;

            if nums[mid] == target {
                return mid as i32;
            }

            // Determine which half is sorted
            if nums[left as usize] <= nums[mid] {
                // Left half is sorted
                if nums[left as usize] <= target && target < nums[mid] {
                    // Target is in sorted left half
                    right = mid as i32 - 1;
                } else {
                    // Target is in right half
                    left = mid as i32 + 1;
                }
            } else {
                // Right half is sorted
                if nums[mid] < target && target <= nums[right as usize] {
                    // Target is in sorted right half
                    left = mid as i32 + 1;
                } else {
                    // Target is in left half
                    right = mid as i32 - 1;
                }
            }
        }

        -1
    }
}

Go

search_in_rotated_sorted_array_binary_search.go

package main

/*
#33 Search in Rotated Sorted Array - Binary Search Approach
Time: O(log n), Space: O(1)

A rotated sorted array has been rotated at an unknown pivot.
Use binary search to find target, identifying which half is sorted.
*/

func SearchInRotatedSortedArrayBinarySearch(nums []int, target int) int {
  /*
  Binary search on rotated array.
  Determine which half is sorted, then check if target is in that half.
  */
  left, right := 0, len(nums)-1

  for left <= right {
    mid := left + (right-left)/2

    if nums[mid] == target {
      return mid
    }

    // Determine which half is sorted
    if nums[left] <= nums[mid] {
      // Left half is sorted
      if nums[left] <= target && target < nums[mid] {
        // Target is in sorted left half
        right = mid - 1
      } else {
        // Target is in right half
        left = mid + 1
      }
    } else {
      // Right half is sorted
      if nums[mid] < target && target <= nums[right] {
        // Target is in sorted right half
        left = mid + 1
      } else {
        // Target is in left half
        right = mid - 1
      }
    }
  }

  return -1
}

Approach 2: Linear Search

✓ Simple

Iterate through the array and check if each element matches the target. Return the index on match or -1 if not found.

⏱ Time O(n) Full array scan 💾 Space O(1) Only pointers

Step-by-step Example

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

i	nums[i]	Match?	Action
0	4	No	Continue
1	5	No	Continue
2	6	No	Continue
3	7	No	Continue
4	0	Yes	Return 4 ✓

Pseudocode

function search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

Solution Code

Python

search_in_rotated_sorted_array_linear.py

"""
#33 Search in Rotated Sorted Array - Linear Search Approach
Time: O(n), Space: O(1)

Linear scan through array to find target value.
"""


class Solution:
    def search(self, nums: list[int], target: int) -> int:
        """
        Simple linear search through array.
        Return index if found, otherwise -1.
        """
        for i in range(len(nums)):
            if nums[i] == target:
                return i

        return -1


# Test cases
if __name__ == "__main__":
    sol = Solution()

    assert sol.search([4, 5, 6, 7, 0, 1, 2], 0) == 4
    assert sol.search([4, 5, 6, 7, 0, 1, 2], 3) == -1
    assert sol.search([1], 1) == 0
    assert sol.search([1, 3], 3) == 1
    assert sol.search([3, 1], 3) == 0

    print("All test cases passed!")

C++

search_in_rotated_sorted_array_linear.cpp

#include <vector>
using namespace std;

/*
#33 Search in Rotated Sorted Array - Linear Search Approach
Time: O(n), Space: O(1)

Linear scan through array to find target value.
*/

class Solution {
public:
    int search(vector<int>& nums, int target) {
        /*
        Simple linear search through array.
        Return index if found, otherwise -1.
        */
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                return i;
            }
        }

        return -1;
    }
};

Java

SearchInRotatedSortedArrayLinear.java

/*
#33 Search in Rotated Sorted Array - Linear Search Approach
Time: O(n), Space: O(1)

Linear scan through array to find target value.
*/

class Solution {
    public int search(int[] nums, int target) {
        /*
        Simple linear search through array.
        Return index if found, otherwise -1.
        */
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }

        return -1;
    }
}

JavaScript

search_in_rotated_sorted_array_linear.js

/**
 * #33 Search in Rotated Sorted Array - Linear Search Approach
 * Time: O(n), Space: O(1)
 *
 * Linear scan through array to find target value.
 */

class Solution {
    search(nums, target) {
        /**
         * Simple linear search through array.
         * Return index if found, otherwise -1.
         */
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] === target) {
                return i;
            }
        }

        return -1;
    }
}

// Export for CommonJS
module.exports = Solution;

Rust

search_in_rotated_sorted_array_linear.rs

/*
#33 Search in Rotated Sorted Array - Linear Search Approach
Time: O(n), Space: O(1)

Linear scan through array to find target value.
*/

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        /*
        Simple linear search through array.
        Return index if found, otherwise -1.
        */
        for (i, &num) in nums.iter().enumerate() {
            if num == target {
                return i as i32;
            }
        }

        -1
    }
}

Go

search_in_rotated_sorted_array_linear.go

package main

/*
#33 Search in Rotated Sorted Array - Linear Search Approach
Time: O(n), Space: O(1)

Linear scan through array to find target value.
*/

func SearchInRotatedSortedArrayLinear(nums []int, target int) int {
  /*
  Simple linear search through array.
  Return index if found, otherwise -1.
  */
  for i := 0; i < len(nums); i++ {
    if nums[i] == target {
      return i
    }
  }

  return -1
}

Common mistakes

Watch for these pitfalls

• Forgetting to identify which half is sorted before making decisions.
• Using <= and < inconsistently in range checks.
• Returning the wrong pointer when target is not in the identified sorted half.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

search_in_rotated_sorted_array_space_optimized.py

"""
Solution for Search in Rotated Sorted Array
"""

def solve():
    """Implementation for approach 3 of Search in Rotated Sorted Array"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

search_in_rotated_sorted_array_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Search in Rotated Sorted Array
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

SearchInRotatedSortedArraySpaceOptimized.java

/**
 * Solution for Search in Rotated Sorted Array
 * Approach 3
 */
public class SearchInRotatedSortedArraySpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

search_in_rotated_sorted_array_space_optimized.js

/**
 * Solution for Search in Rotated Sorted Array
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

search_in_rotated_sorted_array_space_optimized.rs

/// Solution for Search in Rotated Sorted Array
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

search_in_rotated_sorted_array_space_optimized.go

package main

import "fmt"

// Solution for Search in Rotated Sorted Array
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Search in Rotated Sorted Array II ↗ Medium #81
• Find Minimum in Rotated Sorted Array ↗ Medium #153
• Search Insert Position ↗ Easy #35
• Find Peak Element ↗ Medium #162

Interview Tips

Key trade-offs to discuss

• Why identify sorted half? In a rotated array, one half is always sorted. This guides the search efficiently.
• The comparison trick: nums[left] <= nums[mid] tells us if the left half is sorted.
• Range checking: Once you know the sorted half, standard range comparison works.
• Edge cases: Single element, target at boundaries, duplicate handling (not in this version).

← Previous
#32 Longest Valid Parentheses Next
#34 Find First and Last Position of Element in Sorted Array →