Search in Rotated Sorted Array - Video Solutions

Problem Overview: You are given a sorted array that has been rotated at some unknown pivot. The order is still increasing within segments, but the rotation breaks the global order. The task is to locate a target value and return its index in O(log n) time, or -1 if the target does not exist.

Approach 1: Binary Search with Rotation Logic (O(log n) time, O(1) space)

This approach modifies classic Binary Search to work with rotated ordering. During each iteration, compute the midpoint and determine which half of the array is normally sorted. In a rotated array, at least one half between left and mid or between mid and right must remain sorted. Once you identify the sorted side, check whether the target lies within that range. If it does, continue searching there; otherwise move to the other half. The key insight is that the sorted segment gives you a reliable comparison boundary even after rotation. This keeps the search space halving each step, preserving O(log n) time with constant memory.

The algorithm works well because it combines rotation detection and search in a single pass. Each iteration performs simple comparisons and pointer adjustments. No additional preprocessing is required. This is the approach most developers implement in interviews because it demonstrates a strong understanding of conditional search logic and edge handling.

Approach 2: Find Rotated Index and Execute Two Binary Searches (O(log n) time, O(1) space)

This method separates the problem into two clear stages. First, locate the rotation pivot — the index where the smallest element appears. The pivot can be found using a modified binary search that compares mid with the right boundary to determine which half contains the minimum. Once the pivot is identified, the array is effectively split into two sorted subarrays.

Next, run a standard binary search on the appropriate half depending on where the target could exist. If the target lies between the first element and the element just before the pivot, search the left segment; otherwise search the right segment. Because both segments are individually sorted, normal binary search works without additional checks. This technique is conceptually clean and often easier to reason about for beginners studying rotated arrays in Array and Binary Search problems.

Recommended for interviews: The single-pass binary search with rotation logic is typically expected. It achieves O(log n) time without explicitly finding the pivot and shows that you can reason about partially sorted structures. Demonstrating the pivot approach first can help explain the rotation concept, but implementing the single-pass method proves stronger mastery of binary search variants.