Definition
- Search in Rotated Sorted Array – finds the index of a target value in a sorted array rotated at one pivot, in O(log n) time.
- Sorted-half detection – at any split, compare
a[left]toa[mid]to identify which half is properly sorted. - Range check – if the target lies within the sorted half's range, search there; otherwise search the other half.
- O(log n) time, O(1) space – each iteration discards half the remaining elements.
- Not-found path – if the pointers converge without finding the target, return
-1.
The National Bank of India has rotated interest-rate checkpoints and an auditor needs to find the exact position of a specific rate. Looking at the middle checkpoint, the auditor notices that one side is still in perfect ascending order. If the target rate falls inside that orderly side's range, search there; otherwise the target must be on the messy side. Each look halves the remaining checkpoints.
Understanding the Concepts
What is the Search in Rotated Sorted Array problem?
Given a sorted array that has been rotated at some unknown pivot, and a target value, find the index of the target or return -1 if it is not present. For example, searching for 0 in [4, 5, 6, 7, 0, 1, 2] returns index 4.
At the National Bank of India, the treasury team maintains rotated rate checkpoints and needs to locate a specific rate quickly for audit queries.
Why does at least one half remain sorted?
A rotated sorted array split at any middle index always has at least one properly sorted half. The pivot sits in exactly one half, and the other half is cleanly sorted. This is the key observation that makes binary search possible despite the rotation.
How does the algorithm work internally?
You keep left and right indices. At each step, compute mid. If a[mid] equals the target, return mid. Otherwise, determine which half is sorted:
1. If `a[left] <= a[mid]`, the left half `[left..mid]` is sorted. - If `target >= a[left]` AND `target < a[mid]`, search left: `right = mid - 1`. - Otherwise, search right: `left = mid + 1`. 2. If `a[left] > a[mid]`, the right half `[mid..right]` is sorted. - If `target > a[mid]` AND `target <= a[right]`, search right: `left = mid + 1`. - Otherwise, search left: `right = mid - 1`.
Array: [4, 5, 6, 7, 0, 1, 2], target = 0 Step 1: left=0, right=6, mid=3, a[3]=7 a[0]=4 <= a[3]=7 → left half sorted [4,5,6,7] target=0 not in [4,7) → search right: left=4 Step 2: left=4, right=6, mid=5, a[5]=1 a[4]=0 <= a[5]=1 → left half sorted [0,1] target=0 in [0,1) → search left: right=4 Step 3: left=4, right=4, mid=4, a[4]=0 == target → return 4
How do you implement it? (with code)
package com.bank.analysis;
import java.math.BigDecimal;
public class SearchRotatedArray {
public static int search(BigDecimal[] rates, BigDecimal target) {
if (rates == null || rates.length == 0) return -1;
int lo = 0, hi = rates.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (rates[mid].compareTo(target) == 0) {
return mid;
}
// Left half is sorted
if (rates[lo].compareTo(rates[mid]) <= 0) {
if (target.compareTo(rates[lo]) >= 0
&& target.compareTo(rates[mid]) < 0) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
// Right half is sorted
else {
if (target.compareTo(rates[mid]) > 0
&& target.compareTo(rates[hi]) <= 0) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return -1;
}
public static void main(String[] args) {
BigDecimal[] rates = {
new BigDecimal("7.5"), new BigDecimal("8.0"),
new BigDecimal("8.5"), new BigDecimal("3.0"),
new BigDecimal("4.5"), new BigDecimal("6.0")
};
BigDecimal target = new BigDecimal("3.0");
int idx = search(rates, target);
System.out.println("Found at index: " + idx);
}
}
Found at index: 3
How is this different from Find Minimum in Rotated Array?
| Aspect | Find Minimum | Search Target | |---|---|---| | Goal | Locate the pivot (minimum element) | Locate a specific target value | | Decision | Compare mid to right boundary | Detect sorted half, then range-check target | | Return | The minimum value or its index | The target's index or -1 | | Loop condition | `while (lo < hi)` | `while (lo <= hi)` | | Pointer update | `lo = mid + 1` or `hi = mid` | `lo = mid + 1` or `hi = mid - 1` |
What about boundary conditions?
Using <= at the a[left] <= a[mid] comparison correctly treats a two-element window and the case where left equals mid. The target range checks use inclusive bounds on the sorted end and exclusive on mid, which prevents including the mid element twice since it was already checked for equality. Getting these boundaries exactly right is where most buggy implementations fail.
// Correct: inclusive at sorted end, exclusive at mid
if (target.compareTo(rates[lo]) >= 0 && target.compareTo(rates[mid]) < 0)
// Wrong: inclusive on both ends would re-check mid
if (target.compareTo(rates[lo]) >= 0 && target.compareTo(rates[mid]) <= 0)
How do you handle duplicates?
If values can repeat, the comparison of left to mid can be ambiguous when they are equal. When a[left] == a[mid] == a[right], you cannot tell which half holds the target. Resolve it by nudging the left pointer inward by one. This keeps correctness at the cost of a linear worst case.
if (rates[lo].compareTo(rates[mid]) == 0
&& rates[mid].compareTo(rates[hi]) == 0) {
lo++;
continue;
}
What are the edge cases?
- No rotation – the array is fully sorted; standard binary search logic applies because the left half is always sorted.
- Single element – compare directly, return 0 or -1.
- Target not present – pointers converge without a match, return -1.
- Target at boundaries – the inclusive bounds on sorted ends handle first and last elements.
What are common interview follow-up questions?
- What if there are duplicates? – Nudge left when all three are equal, accept O(n) worst case.
- Can you find the rotation count? – Yes, the index of the minimum element is the rotation count.
- What if the target appears multiple times? – This returns any one index; for all indices you would need additional scanning.
- Time and space? – O(log n) time for distinct values, O(1) space.
Visual Overview
┌─────────────────────────────────────────────────────┐ │ Search in Rotated Sorted Array Decision Tree │ ├─────────────────────────────────────────────────────┤ │ │ │ a[mid] == target? ──YES──→ Return mid │ │ │ NO │ │ ▼ │ │ a[left] <= a[mid]? │ │ YES → Left half sorted │ │ │ target in [a[left], a[mid])? │ │ │ YES → hi = mid - 1 │ │ │ NO → lo = mid + 1 │ │ NO → Right half sorted │ │ │ target in (a[mid], a[right]]? │ │ │ YES → lo = mid + 1 │ │ │ NO → hi = mid - 1 │ │ │ │ Loop until lo > hi → return -1 (not found) │ └─────────────────────────────────────────────────────┘
Key Takeaway
Search in Rotated Sorted Array finds the index of a target in a sorted array that has been rotated at one pivot, and you solve it with binary search in O(log n) time and O(1) space. The key observation is that when you split a rotated array at any middle index, at least one half is always properly sorted, so at each step you detect which half is sorted and use a precise range test to decide whether the target lives there.
Concretely, if the left element is less than or equal to the middle, the left half is sorted, and you check whether the target is at least the left value and strictly below the middle; if so you keep the left half, otherwise the right. If the left is greater than the middle, the right half is sorted and you do the symmetric check. Identifying the sorted half is what lets ordinary range reasoning work despite the rotation.
The part that catches people is the inclusive and exclusive boundaries. You use inclusive bounds on the sorted end and exclusive bounds at the middle so the middle element, which you already tested for equality, is never considered twice, and you use less-than-or-equal when comparing left to middle so two-element windows resolve correctly. For duplicates you nudge the left pointer inward when all three are equal, accepting a linear worst case.
In a banking project at the National Bank of India, this is used on rotated interest-rate checkpoints so an audit feature can find the exact index of a given rate and report cleanly when a rate is absent.
Remember one sentence: Detect which half is sorted, range-check the target against that half, and discard the other half to search a rotated array in O(log n) time.
---