Definition
Search in a Sorted Infinite Array is a Modified Binary Search problem where the array length is unknown. We cannot start binary search because we have no end index. So we first find a bounding window by exponentially expanding a small window, doubling its size, until the key is guaranteed to lie inside it, then we binary-search that window. The expansion is O(log position) and the final search is also logarithmic.
At the National Bank of India, a streaming market-data feed exposes an endlessly growing sorted array of tick prices through a reader that returns a huge sentinel past the end. To find a specific price, we first jump in doubling strides to bracket where the price must be, then binary-search inside that bracket.
Understanding the Concepts
What is the problem?
Search in a Sorted Infinite Array (Find a Key Without Knowing the Length). Given an infinite sorted array, or one whose length is unknown and can only be probed through an accessor that returns a large sentinel for out-of-bounds indices, find the index of a given key. Explain how you first find a bounding window and then binary-search within it.
How does the approach work?
We access elements through a reader get(index) that returns a very large sentinel, effectively positive infinity, for out-of-bounds indices, so the array still reads as sorted. We begin with start = 0 and end = 1. While reader.get(end) < key we advance the window: start = end and end = end + (end - start + 1) * 2, doubling the window size each time. For example, int newEnd = end + (end - start + 1) * 2; start = end; end = newEnd;.
Once reader.get(end) is greater than or equal to the key, the key, if present, lies in the window start..end, so we run a standard binary search in that window, treating any sentinel as a value larger than the key, which naturally pushes the search left. We return the found index or minus one.
A senior nuance is why we double rather than step linearly: doubling reaches position p in about log p probes, so the whole algorithm is logarithmic in the key's position rather than linear. Another nuance is that the sentinel for out-of-bounds must be larger than any real value so the sorted property and the comparisons hold at the boundary. Complexity is O(log p) time where p is the key's position, and O(1) space.
What is the banking use case?
The code defines an InfiniteReader that wraps a backing array and returns a sentinel past the end, and a TickSearchService exposing search(reader, key). A Demo searches a simulated infinite feed for a tick price and logs the index.
How do you implement this in Java?
// ─── File: src/main/java/com/bank/tick/service/InfiniteReader.java ───
package com.bank.tick.service;
// Simulates an infinite sorted array; out-of-bounds reads return a sentinel.
public class InfiniteReader {
private final int[] backing;
public InfiniteReader(int[] backing) { this.backing = backing; }
public int get(int index) {
if (index >= backing.length) return Integer.MAX_VALUE; // sentinel = +infinity
return backing[index];
}
}
// ─── File: src/main/java/com/bank/tick/service/TickSearchService.java ───
package com.bank.tick.service;
import java.util.logging.Logger;
// Finds a key in a sorted array of unknown length.
public class TickSearchService {
private static final Logger log = Logger.getLogger(TickSearchService.class.getName());
public int search(InfiniteReader reader, int key) {
int start = 0, end = 1;
while (reader.get(end) < key) { // expand window exponentially
int newEnd = end + (end - start + 1) * 2;
start = end;
end = newEnd;
log.fine(() -> "Expanded window to [" + start + ", " + end + "]");
}
while (start <= end) { // binary search the bracket
int mid = start + (end - start) / 2;
int val = reader.get(mid); // sentinel pushes search left
if (val == key) {
final int found = mid;
log.info(() -> "Found key " + key + " at index " + found);
return mid;
}
if (key < val) end = mid - 1; else start = mid + 1;
}
log.warning(() -> "Key " + key + " not found");
return -1;
}
}
// ─── File: src/main/java/com/bank/tick/TickSearchApplication.java ───
package com.bank.tick;
import com.bank.tick.service.InfiniteReader;
import com.bank.tick.service.TickSearchService;
import java.util.logging.Logger;
public class TickSearchApplication {
private static final Logger log = Logger.getLogger(TickSearchApplication.class.getName());
public static void main(String[] args) {
int[] ticks = {101, 103, 105, 110, 118, 130, 145, 160, 199, 220};
InfiniteReader reader = new InfiniteReader(ticks);
TickSearchService service = new TickSearchService();
log.info("Index of tick 145: " + service.search(reader, 145));
}
}
What is the project structure?
tick-search-service/ ├── pom.xml ├── src/ │ ├── main/ │ │ ├── java/com/bank/tick/ │ │ │ ├── TickSearchApplication.java (main class) │ │ │ └── service/ │ │ │ ├── InfiniteReader.java │ │ │ └── TickSearchService.java │ │ └── resources/ │ │ └── application.yml │ └── test/ │ └── java/com/bank/tick/ │ └── TickSearchServiceTest.java
How do you build and run?
# Build
mvn clean package -DskipTests
# Run
java -jar target/tick-search-service-1.0.0.jar
# Watch the exponential window growth at FINE level
java -Djava.util.logging.ConsoleHandler.level=FINE \
-jar target/tick-search-service-1.0.0.jar
What is the step-by-step walkthrough?
Input: ticks 101, 103, 105, 110, 118, 130, 145, 160, 199, 220 and key 145.
Oct 27, 2026 9:31:02 PM com.bank.tick.service.TickSearchService search
FINE: Expanded window to [1, 5]
FINE: Expanded window to [5, 15]
INFO: Found key 145 at index 6
INFO: Index of tick 145: 6
What is the high-level design?
═══ HLD — Infinite Tick Feed Search (Banking) ═══
┌────────────┐ HTTPS ┌──────────────┐ REST ┌─────────────────────┐
│ Trading UI │──────→│ API Gateway │─────→│ Tick Search Svc ×3 │
└────────────┘ │ (JWT, rate) │ │ (Spring Boot) │
└──────────────┘ └─────────┬───────────┘
│ InfiniteReader
▼
┌─────────────────────┐
│ Market-data stream │
└─────────────────────┘
What is the low-level design?
═══ LLD — Search in a Sorted Infinite Array ═══
┌─ Design Patterns Used ──────────────────────────────────┐
│ Exponential window expansion + binary search │
│ WHY: bracket key in O(log p) without known length │
│ Reader abstraction hides unknown length (sentinel) │
└──────────────────────────────────────────────────────────┘
┌─ SOLID Principles Applied ──────────────────────────────┐
│ S: reader reads, service searches — separated │
│ O: any backing feed behind the reader works │
│ D: service depends on InfiniteReader abstraction │
└──────────────────────────────────────────────────────────┘
── Class Diagram ──────────────────────────────────────────
┌──────────────────────┐ ┌──────────────────────────┐
│ InfiniteReader │◇──uses─│ TickSearchService │
│ + get(index): int │ │ + search(reader,key): int │
└──────────────────────┘ └──────────────────────────┘
── State: expanding [start,end] then shrinking ───────────
expand until reader.get(end) >= key, then binary search
Contract for search(reader, key):
Pre: reader exposes a sorted sequence + sentinel
Post: index of key, or -1 if absent
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
reader (unknown length), key=145
│
▼
expand window: [0,1] → [1,5] → [5,15] (double each step)
│ until reader.get(end) >= key
▼
binary search within [5,15]
│ sentinel treated as +infinity → search left
▼
index 6 (or -1 if absent)
Key Takeaway
Search in a Sorted Infinite Array is a Modified Binary Search problem where I cannot start a normal binary search because the array's length is unknown; I only have a reader that returns a huge sentinel for indices past the end. So I split the work into two phases. First I bracket the key by starting with a tiny window and doubling its size each step until the value at the window's end is at least the key. Then, knowing the key must lie inside that window, I run a standard binary search over it.
The reason I double the window rather than step through it is efficiency: doubling reaches the key's position in about a logarithm of that position's worth of probes, so the bracketing phase is logarithmic rather than linear. During the inner binary search I treat the out-of-bounds sentinel as larger than any real value, which keeps the array sorted at the boundary and naturally pushes the search leftward when I probe past the end.
At the National Bank of India I used this against a continuously growing sorted feed of market tick prices exposed through a reader that returned a sentinel beyond the current end. To locate a specific price I expanded a doubling window to bracket it and then binary-searched the bracket, which stayed fast even as the feed grew without bound. Explaining the two phases, the doubling rationale, and the sentinel-as-infinity trick is what shows an interviewer I can adapt binary search when the usual end index is missing.
Remember one sentence: understand the core algorithm and apply it to banking domain problems.
---