Search Rotated Sorted Array | Java Fresher Interview
Fast recall
Quick revision
Core answer
mid, decide which half (left or right of mid) is sorted by comparing endpoints, then check whether the target lies inside that sorted half's range: if yes search it, otherwise search the other half. Each step still halves the array, so it's O(log n).Whether you can spot and exploit the 'one half is always sorted' invariant instead of giving up on binary search
Reverting to an O(n) linear scan, or using strict < so the left == mid single-element case is misclassified
State the invariant explicitly and use nums[left] <= nums[mid] to detect the sorted half safely
Interview-ready guide
Interview answer
Searching a rotated sorted array is a nice example of adapting binary search by spotting an invariant.
A rotated array is just a sorted array that's been cut at some pivot and the two pieces swapped, like four five six seven zero one two. The invariant I rely on is that no matter where I compute the middle, at least one of the two halves, the part left of mid or the part right of mid, is still perfectly sorted.
So at each step I first check if the middle is the target. If not, I figure out which half is sorted by comparing endpoints. If nums at low is less than or equal to nums at mid, the left half is sorted; otherwise the right half is.
Once I know which half is sorted, I check whether the target's value falls inside that half's range. If it does, I search that half; if it doesn't, the target must be in the other half, the one that contains the rotation point, so I search there. Either way I throw away half the array, so I keep the O of log n time.
Two details I'm careful about. I use less than or equal when comparing the low endpoint to mid, because with a strict less than the single-element case where low equals mid gets misclassified. And I always check that the target is actually between the sorted half's two endpoints, not just on one side of mid.
The common mistake is panicking and reverting to a linear scan, but the rotation only creates one break, and identifying the sorted half lets binary search keep working. If the array can contain duplicates, I'd note the worst case can slip to O of n.
Search Rotated Sorted Array | Java Fresher Interview
Direct Answer
In a rotated sorted array, at every step at least one half is normally sorted. Compute mid, decide which half (left or right of mid) is sorted by comparing endpoints, then check whether the target lies inside that sorted half's range: if yes search it, otherwise search the other half. Each step still halves the array, so it's O(log n).
Deep Dive & Architecture
A rotated sorted array is made from two sorted runs. With distinct values, at least one half around the midpoint is still sorted. That fact tells us which half can contain the target.
Worked example: [4, 5, 6, 7, 0, 1, 2], target 0
The first midpoint is value 7. Because 4 <= 7, the left half is sorted. Target 0 is not between 4 and 7, so discard that half and move left to index 4. The next midpoint is value 1. Its left half [0, 1] is sorted, and 0 lies inside its bounds, so move right leftward. Index 4 now holds 0 and the search succeeds.
Use inclusive comparisons carefully. When the left half is sorted, test a[left] <= target && target < a[mid]. Otherwise, test a[mid] < target && target <= a[right] for the right half. These strict and inclusive boundaries prevent the midpoint from being kept twice.
With distinct elements, one half is unambiguous and the method is O(log n). Many duplicate values can hide which half is sorted—for example [1, 1, 1, 1, 0, 1]—so a duplicate-aware version may need to shrink both ends and can degrade to O(n).
Code Example
int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // left half sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
// nums = {4,5,6,7,0,1,2}, target = 0
// mid=3 (7): left {4..7} sorted, 0 not in [4,7) -> lo=4
// mid=5 (1): left {0,1} sorted, 0 in [0,1) -> hi=4
// mid=4 (0): match -> return 4
Common Mistakes & Pitfalls
- Giving up on binary search: rotation adds one discontinuity, not chaos - O(log n) is still possible.
- Strict
<for the sorted half: usenums[left] <= nums[mid]so the single-element (left == mid) case is handled. - Skipping the range check: you must verify the target is within the sorted half's endpoints, not just on one side of
mid. - Duplicates: equal values can break the endpoint comparison and push worst case to O(n) - mention it.
Check your understanding
Answer these without looking back at the article.
- How does binary search work and what is its time complexity?
- Why do you use mid = left + (right - left) / 2 instead of (left + right) / 2 in binary search?
- Can binary search be applied to problems other than searching in sorted arrays?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.