ToolMight LogoToolMight
MediumBinary SearchPattern: Modified Binary SearchPattern: Halved Sorted Invariant

Search in Rotated Sorted Array

Search a rotated sorted array in O(log n) time. A masterclass in applying binary search when global order is broken: at least one half is always guaranteed to be sorted.

Problem Statement

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.

Examples & Constraints

Example 1
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Explanation: 0 is at index 4 in the rotated array.
Example 2
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Explanation: 3 does not exist in nums.
Constraints
  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.

Modified Binary Search (Sorted Half Check)

Optimal Approach
Time:O(log n)
Space:O(1)

Divide the array at midpoint. One of the two halves is always strictly sorted. Determine which half is sorted, then check if target falls inside its boundaries.

Time ComplexityO(log n)

Halves the active search window at each step.

Space ComplexityO(1)

Operates with pointer scalars in constant auxiliary space.

Underlying algorithmic logic

The Core Mental Model: One Half Is ALWAYS Normal

Take a sorted array like [0, 1, 2, 4, 5, 6, 7]. If you slice it anywhere and swap the segments (e.g. [4, 5, 6, 7, 0, 1, 2]), notice this immutable mathematical truth:

No matter where the rotation occurred, at least ONE of the two halves is guaranteed to be completely normally sorted.

Anchor To The Normal Half

Standard binary search requires the entire array to be sorted. Here, we adapt:

  1. Calculate mid = left + (right - left) / 2.
  2. If nums[mid] == target, return mid.
  3. Check which half is normally sorted:
  • Is the LEFT half sorted? (nums[left] <= nums[mid]):
  • Does our target sit inside that sorted left range? (nums[left] <= target < nums[mid]):
  • If yes: target must be in the left half -> right = mid - 1.
  • If no: target must be in the right half -> left = mid + 1.
  • Otherwise, the RIGHT half is guaranteed to be sorted:
  • Does our target sit inside that sorted right range? (nums[mid] < target <= nums[right]):
  • If yes: target must be in the right half -> left = mid + 1.
  • If no: target must be in the left half -> right = mid - 1.

Because we discard half of the remaining elements on every single iteration, we preserve pure `O(log n)` logarithmic runtime without ever needing to find the rotation pivot index first.

Step-by-step execution walkthrough

1
Initial State

nums = [4, 5, 6, 7, 0, 1, 2], target = 0. left = 0, right = 6.

left = 0, right = 6
2
Midpoint Evaluation

mid = 3 (nums[3] = 7). Left half [4, 5, 6, 7] is sorted because nums[0] <= nums[3]. Target 0 is NOT between 4 and 7, so target must be in right half. Set left = 4.

left = 4, right = 6
3
Second Evaluation

mid = 5 (nums[5] = 1). nums[4] is 0. Target 0 < 1. Set right = 4.

left = 4, right = 4
4
Target Matched

mid = 4. nums[4] == 0 === target. Return 4.

mid = 4 -> return 4
Advantages
  • •Optimal O(log n) efficiency
  • •Constant O(1) space
  • •No need to locate the rotation pivot explicitly first
Trade-offs
  • •Boundary equality conditions require careful implementation

Code Implementations

Copy & paste production-ready solutions for Modified Binary Search (Sorted Half Check) in your language of choice

File: solution.py
Python
def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1
if __name__ == "__main__":
    nums = [4, 5, 6, 7, 0, 1, 2]
    print(f"search for 0: {search(nums, 0)}")
    print(f"search for 3: {search(nums, 3)}")
Interactive visualizer available

Understand Binary Search Visually

Divide and conquer sorted datasets, converging left/right indices to isolate target values. Test live edge cases and watch memory state transitions step-by-step.

Launch Binary Search Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyBinary Search
Visualizer

Binary Search

Locate a target value in a sorted array in O(log n) logarithmic time. Like opening a dictionary in the middle, each comparison eliminates half the remaining items.

2 approaches(O(log n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic