What is the best approach to solve Search in Rotated Sorted Array?

The optimal approach for Search in Rotated Sorted Array is the "Optimal — Modified Binary Search" technique. It runs in O(log n) time and uses O(1) space. In a rotated array, one half is always fully sorted. Determine which half: if nums[lo] ≤ nums[mid], the left half is sorted. Check if target falls in the sorted half; if yes, search there, else search

What is the time complexity of Search in Rotated Sorted Array?

The optimal solution for Search in Rotated Sorted Array has a time complexity of O(log n) and a space complexity of O(1), achieved using the Binary Search pattern.

Is Search in Rotated Sorted Array a Medium LeetCode problem?

Yes, LeetCode #33 (Search in Rotated Sorted Array) is rated Medium. It uses the Binary Search pattern and is commonly asked in interviews at Amazon, Google, Microsoft.

How to solve Search in Rotated Sorted Array in Python, Java, C++, and JavaScript?

LumiChats provides complete solutions for Search in Rotated Sorted Array in Python, Java, C++, and JavaScript, along with step-by-step visual animations and time/space complexity analysis. All solutions are free to view.

#33MediumBinary Search

Search in Rotated Sorted Array

At least one half is always sorted — use that to decide where to search.

AmazonGoogleMicrosoftUberBloomberg

Problem Statement

Given a rotated sorted array nums (with no duplicates) and a target integer, return the index of target if it exists, otherwise return -1. You must write an algorithm with O(log n) runtime.

Examples

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

Constraints

1 ≤ nums.length ≤ 5000
−10⁴ ≤ nums[i], target ≤ 10⁴
All values are unique.

Solutions

Linear Search

TimeO(n)SpaceO(1)

Scan the array for target. O(n). Ignores the sorted property.

Visual Animation

def search(nums, target):
    try: return nums.index(target)
    except: return -1

Related Concepts

Deepen your understanding with these related topics from our AI Glossary:

Machine Learning Browse all 190+ concepts →

Deepen your understanding

Want to master the core concepts?

Our free AI Glossary covers 190+ topics — from Binary Search to Dynamic Programming, Machine Learning, SQL, and more. Structured learning tracks for every level.

Browse AI Glossary All Problems

39+

AI Models

₹69

Per day used

Languages

Stuck? Ask AI to explain it step by step.

Ask Claude, GPT-4o, or Gemini to debug your code, generate test cases, or walk through the intuition. 39+ models. Pay only on days you use it — no subscription required.

Free to start · No credit card required to explore

Get Started Free

Back to all problems