beingsde
Sign In
Back to all DSA patterns
Binary Search•Pattern: Binary Search•Medium

Search in rotated sorted array

Problem Intuition & Objective

Find a target in a rotated sorted array in O(log n).

Time ComplexityO(log n)
Optimal
Space ComplexityO(1)
Memory Bounds
Optimal Algorithmic Approach

Modified binary search: at each step, identify the sorted half and check if target belongs there.

Core Invariants & Edge Cases

  • One half is always sorted; determine which half and narrow search
  • If nums[mid] >= nums[left]: left half is sorted
  • Check if target falls in the sorted half; otherwise search the other half
Previous ProblemNumber of 1 bits (Hamming weight)Next Problem Find minimum in rotated sorted array

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.