Search in Infinite Sorted Array
Mahabharata — The Boundless Formation — Finding a Warrior When the Army Has No Known End
अनन्तं सैन्यं — सीमा अज्ञाता। द्विगुणेन विस्तारयेत् — यावत् लक्ष्यं न दृश्यते॥
*The army is boundless — its end unknown. Double the range each time — until the target is seen.*
The Story
Given an infinite sorted array (you can access any index but don't know the length), find the target.
The challenge: without knowing n, we can't set `right = n-1`. We need to first find a valid search window.
**Exponential Search (doubling):** 1. Start with window [low=0, high=1] 2. While arr[high] < target: `low = high; high *= 2` (double the window) 3. Once arr[high] >= target: the target is in [low, high] — run standard binary search
```java int low = 0, high = 1; while (get(arr, high) < target) { low = high; high *= 2; } // Now binary search in [low, high] while (low <= high) { int mid = low + (high - low) / 2; int val = get(arr, mid); if (val == target) return mid; if (val < target) low = mid + 1; else high = mid - 1; } return -1; ```
For target at index k: the doubling phase runs O(log k) times (high doubles until it passes k). Then binary search in [k/2, 2k] runs O(log k). Total: **O(log k)**.
Arjuna faced an endless formation. He doubled his search range each step — 1, 2, 4, 8, 16, ... — until the range contained the target, then used standard binary search within that window.
**Why doubling works:** At each step, `high` doubles. When high first exceeds the target's index k, we know `k < high = 2 * prev_high`, so the previous `low = prev_high = high/2` is our lower bound. The window [low, high] = [k/2, 2k] contains k and has size at most 2k.
The Linear Scan
Scan from index 0 until finding target. O(k) where k is target's index.
int searchBruteForce(int[] arr, int target) {
for (int i = 0; ; i++)
if (arr[i] == target) return i;
else if (arr[i] > target) return -1;
}Arjuna's Exponential Doubling Wisdom
int searchInfinite(int[] arr, int target) {
int low = 0, high = 1;
// Exponential expansion
while (get(arr, high) < target) {
low = high;
high *= 2;
}
// Standard binary search in found window
while (low <= high) {
int mid = low + (high - low) / 2;
int val = get(arr, mid);
if (val == target) return mid;
if (val < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int get(int[] arr, int i) {
return i < arr.length ? arr[i] : Integer.MAX_VALUE;
}Step-by-Step Walkthrough
arr=[2,5,8,11,...], target=5 high=1(arr[1]=5>=5): stop immediately. BinarySearch[0,1]: mid=0(2<5)→lo=1. mid=1(5==5)→return 1 ✅
Deep Insight
**Complexity analysis:** If target is at index k, doubling reaches k after ceil(log₂k) steps. Window size is ≤ 2k, so binary search is O(log k). Total: O(log k).
**The `get()` helper:** Returns MAX_VALUE for out-of-bounds indices. This ensures the exponential phase terminates correctly for truly infinite arrays and for finite arrays where high might overshoot.
**Real-world application:** Infinite or size-unknown streams where elements arrive in sorted order and you need to locate a specific value efficiently.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(k) | O(1) | k = index of target |
| Optimal | O(log k) | O(1) | O(log k) doubling + O(log k) binary search |
Pattern Recognition
✅ Unknown array size — exponential search first ✅ Double high until arr[high] >= target ✅ Then standard binary search in [low, high] ✅ Use MAX_VALUE for out-of-bounds access **LeetCode Trigger Phrases:** → "infinite sorted array" / "unbounded sorted array" → "exponential search" → Find target when array size unknown
Bhagavad Gita 11.40
अनन्तवीर्यामितविक्रमस्त्वं सर्वं समाप्नोषि ततोऽसि सर्वः।
You are of infinite power and boundless might; You pervade everything and are therefore everything.
Connection: The infinite sorted array mirrors the boundless — its true extent hidden from the searcher. Like the seeker who cannot grasp the full extent of the divine but approaches through successive approximations, the exponential search doubles its window at each step — first finding the approximate region, then refining with precision. The unknown end is not a barrier but a challenge met by progressively expanding awareness.