PPractick

The problem

A circular log buffer stores message IDs in increasing order, but because it wraps around, the array in memory looks like [4, 5, 6, 7, 0, 1, 2]: sorted, then rotated at an unknown point. Given an ID, the system must find its index in O(log n). Plain binary search fails because the array isn't sorted as a whole, but at every midpoint at least one half is sorted. Check whether the target lies inside that sorted half's range, and you know which half to discard.

Example: [4, 5, 6, 7, 0, 1, 2], target 0 → 4.

Function signature

int searchRotated(const vector<int>& nums, int target);  // distinct values; index or -1

Test cases

Input (nums, target)	Output	Explanation
([4, 5, 6, 7, 0, 1, 2], 0)	4
([4, 5, 6, 7, 0, 1, 2], 3)	-1	Not present
([1], 0)	-1
([1], 1)	0
([3, 1], 1)	1	Two elements, rotated
([5, 1, 3], 5)	0
([4, 5, 6, 7, 8, 1, 2, 3], 8)	4	Just before the rotation point

(Confirm: the values are distinct and the array is a rotation of an increasing array; O(log n) is required.)

How interviewers phrase it

• "Search for a target in a rotated sorted array" (LeetCode 33).
• Follow-ups: with duplicates (S.No 110), find the minimum (S.No 111), count the rotations (S.No 112).

Clarifying questions to ask

1. Are the values distinct? (Duplicates break the "which half is sorted" test.)
2. What should be returned if the target is absent?
3. Is the rotation amount unknown?

Follow-ups to expect

1. "How do you know which half is sorted?"
2. "Then how do you decide where to go?"
3. "Could you find the rotation point first?"
4. "What breaks with duplicates?"
5. "Complexity?"

Related questions

• Search in rotated sorted array-II Medium
• Find minimum in Rotated Sorted Array Medium
• Find out how many times the array is rotated Easy
• First and last occurrence Medium
• Single element in a Sorted Array Medium
• Find peak element Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in