Definition
Searching a rotated sorted array uses a modified binary search where, at each step, exactly one of the two halves around the middle is normally sorted. We identify the sorted half, check whether the target lies within its sorted range, and discard the half that cannot contain the target. This runs in O(log n) time and O(1) space.
The bank's sorted rate card was cut and the front moved to the back, so it reads high-to-higher, then drops, then low-to-higher again. To find a specific rate, the clerk looks at the middle. One side of the middle is always cleanly sorted. If the target fits inside that clean side's range, he searches there; otherwise he searches the messy side, which contains the cut.
Understanding the Concepts
What is the problem?
Search in Rotated Sorted Array — Decide Which Half Is Sorted. A sorted ascending array of distinct integers is rotated at an unknown pivot. Given a target, return its index or minus one if absent. Run in logarithmic time.
How does the approach work?
The key observation is that after rotation, when you split at the middle, at least one half from low to mid or mid to high is still fully sorted. We detect which half is sorted by comparing endpoints.
The loop is while (low <= high) with the overflow-safe mid. First check the match: if (arr[mid] == target) return mid;.
Then determine the sorted half. If arr[low] <= arr[mid], the left half is sorted. In that case, if arr[low] <= target && target < arr[mid], the target is inside the sorted left half, so high = mid - 1; otherwise low = mid + 1.
If instead the left half is not sorted, then the right half is sorted. If arr[mid] < target && target <= arr[high], the target is inside the sorted right half, so low = mid + 1; otherwise high = mid - 1.
This way each step still discards half the array, preserving logarithmic time. The careful part is using inclusive and exclusive bounds correctly in the range checks, which is why the comparisons mix less-than and less-than-or-equal precisely.
A senior-level nuance is why exactly one half is always sorted: the single rotation point lies in only one half, and the other half spans a contiguous ascending run. Identifying the sorted half and using its clean range to test the target is what lets us decide with certainty.
Another nuance is the duplicate follow-up. With duplicates, arr[low] equals arr[mid] no longer guarantees the left half is sorted, so you must advance low by one in that ambiguous case, which degrades the worst case to linear. With distinct values the clean logarithmic version holds.
What is the banking use case?
In the code: a ReferenceLocator holds a rotated int array of reference numbers. A search method performs the sorted-half binary search. A RotatedSearchDemo main finds a present reference and a missing one.
How do you implement this in Java?
// ─── File: RotatedSearchDemo.java ───
// Multiple classes in one file for the runnable demo.
package com.bank.reference;
import java.util.logging.*;
public class RotatedSearchDemo {
private static final Logger log = Logger.getLogger(RotatedSearchDemo.class.getName());
static {
LogManager.getLogManager().reset();
ConsoleHandler handler = new ConsoleHandler();
handler.setFormatter(new BankLogFormatter());
log.addHandler(handler);
log.setLevel(Level.ALL);
}
public static void main(String[] args) {
// Sorted reference numbers rotated at an offset
int[] refs = {40, 50, 60, 70, 10, 20, 30};
ReferenceLocator locator = new ReferenceLocator();
log.info("Searching for reference 20 (present)");
log.info("Index -> " + locator.search(refs, 20));
log.info("Searching for reference 55 (absent)");
log.info("Index -> " + locator.search(refs, 55));
}
}
// ─── Would be in service/ReferenceLocator.java ───
class ReferenceLocator {
// Modified binary search over a rotated sorted array. O(log n), O(1).
int search(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // overflow-safe
if (arr[mid] == target) return mid;
if (arr[low] <= arr[mid]) {
// Left half [low..mid] is sorted
if (arr[low] <= target && target < arr[mid]) {
high = mid - 1; // target in sorted left
} else {
low = mid + 1; // target in the other half
}
} else {
// Right half [mid..high] is sorted
if (arr[mid] < target && target <= arr[high]) {
low = mid + 1; // target in sorted right
} else {
high = mid - 1; // target in the other half
}
}
}
return -1; // not present
}
}
// ─── Would be in util/BankLogFormatter.java ───
class BankLogFormatter extends java.util.logging.Formatter {
@Override
public String format(java.util.logging.LogRecord record) {
return String.format("%1$tF %1$tT [%2$s] %3$s%n",
new java.util.Date(record.getMillis()),
record.getLevel().getName(),
record.getMessage());
}
}
What is the project structure?
reference-locator-service/ ├── pom.xml ├── src/ │ ├── main/ │ │ ├── java/com/bank/reference/ │ │ │ ├── RotatedSearchDemo.java (main class / runnable demo) │ │ │ ├── service/ │ │ │ │ └── ReferenceLocator.java │ │ │ └── util/ │ │ │ └── BankLogFormatter.java │ │ └── resources/ │ │ └── application.yml │ └── test/ │ └── java/com/bank/reference/ │ └── ReferenceLocatorTest.java
How do you build and run?
# Compile
javac RotatedSearchDemo.java
# Run
java com.bank.reference.RotatedSearchDemo
What is the step-by-step walkthrough?
Input: refs 40, 50, 60, 70, 10, 20, 30 (indices 0 to 6). Target 20, which is at index 5.
For target 55: step 1 left half sorted 40 to 70, is 55 in range 40 to below 70? Yes, so high becomes 2. Then we search the left part 40, 50, 60 and never find 55, eventually low exceeds high, return minus one.
Final output:
2026-10-26 22:30:00 [INFO] Searching for reference 20 (present)
2026-10-26 22:30:00 [INFO] Index -> 5
2026-10-26 22:30:00 [INFO] Searching for reference 55 (absent)
2026-10-26 22:30:00 [INFO] Index -> -1
What is the high-level design?
═══ HLD — Transaction Reference Locator ═══
┌──────────┐ REST ┌─────────────────────┐ in-mem ┌──────────────┐
│ Support │─────→│ Reference Locator │───────→│ rotated ref │
│ Console │ │ search() O(log n) │ │ array (PG) │
└──────────┘ └─────────┬───────────┘ └──────────────┘
▼ found → fetch txn detail
Observability: ELK logs, Prometheus locate-latency
What is the low-level design?
═══ LLD — Search in Rotated Sorted Array ═══ ┌─ Design Patterns Used ───────────────────────────────────┐ │ Binary search with sorted-half detection │ │ Decide branch by comparing arr[low] vs arr[mid] │ └──────────────────────────────────────────────────────────┘ ┌─ SOLID ──────────────────────────────────────────────────┐ │ S: ReferenceLocator only searches │ │ O: comparison keys swappable for other sortable refs │ └──────────────────────────────────────────────────────────┘ ┌──────────────────────────────────────┐ │ ReferenceLocator │ │ + search(arr, target): int │ O(log n), O(1) │ identifies sorted half each step │ └──────────────────────────────────────┘ Call chain: 1. search(arr, 20) 2. mid match? no 3. left sorted? yes → target in range? no → low=mid+1 4. mid==target → return 5
What is the time and space complexity?
Analyze the solution based on the algorithm used. Consider both the time to process input and the space required for any data structures.
What are common mistakes?
Common mistakes include off-by-one errors, not handling edge cases like empty input, and not considering the constraints of the problem.
What are the edge cases?
Edge cases include empty input, single element input, all identical elements, and boundary values.
What should a senior engineer know?
A senior engineer should understand the time-space tradeoffs, be able to explain the algorithm clearly, and know when this technique applies versus alternatives.
Visual Overview
Input: [40 50 60 70 | 10 20 30] target 20
│
▼ mid=3 (70). left [40..70] sorted. 20 in [40,70)? no → go right
low=4 high=6 mid=5 (20) == target
│
▼
Output: index 5 (each step one half is sorted → discard other half)
Key Takeaway
Searching a rotated sorted array is a modified binary search that leans on one crucial fact: no matter where you split at the middle, at least one of the two halves is still fully sorted. So on each step I first check whether the middle is the target, and if not, I figure out which half is sorted by comparing the low element to the middle element. If the low element is less than or equal to the middle, the left half is a clean ascending run; otherwise the right half is.
Once I know which half is sorted, I can test the target against that half's known range with certainty. If the target falls inside the sorted half's range, I search there; if not, I search the other half, which is the one containing the rotation point. Either way I discard half the array per step, so the search stays logarithmic even though the array as a whole is not sorted.
In my banking project at National Bank of India, the archival system stores sorted transaction reference numbers starting from an arbitrary offset, which rotates the sequence. Support staff need to locate a specific reference fast to pull up a transaction, and this algorithm finds it logarithmically despite the rotation, where a linear scan over a large reference list would be far too slow.
The detail I am always careful about is getting the range comparisons exactly right, mixing less-than and less-than-or-equal correctly so the inclusive boundaries line up, because an off-by-one there sends the search down the wrong half. I also mention the duplicate follow-up: if values can repeat, the low-equals-middle case no longer proves the left half is sorted, so I have to advance low by one and accept a linear worst case, but with distinct references the clean logarithmic version applies.
Remember one sentence: understand the core algorithm and apply it to banking domain problems.
---