Log inSign up
mediumgfgNot Started

Search in a Sorted Infinite Array

Given an infinite sorted array (or an array of unknown large size) and an element key to search, find the index of key in O(log p) time where p is the position of the key.

Binary Search
Solve on gfg
Lesson

Problem Statement

Suppose you have a sorted array of infinite numbers, how would you search an element in the array?\n\nSince the array is considered infinite, you do not have access to array.length or bounds. You can only query reader.get(i) or arr[i]. If the element is present in the array, return its index; otherwise, return -1.\n\nYou must design an algorithm that runs in O(log p) time, where p is the index position of the target element.

Example 1 · Example 1: Target Present:

Input: arr = [3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170, ...], target = 10
Output: 4
Explanation: Element 10 appears at index 4.

Example 2 · Example 2: Target not in infinite array:

Input: arr = [2, 4, 6, 8, 10, 12, ...], target = 7
Output: -1
Explanation: Element 7 is not in the array.

Constraints:

  • The array is sorted in ascending order.
  • The array size is unbounded / infinite.
  • -109 <= arr[i], target <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand exponential search for bounding unbounded domains.
  • Combine range expansion with binary search to achieve O(log p) complexity.
  • Avoid out-of-bounds errors when interfacing with infinite/reader structures.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sorted array without known upper bound or infinite stream.
  • Constraint on runtime is O(log p) relative to target position.

Algorithmic Decision Tree:

  • Initialize low = 0, high = 1.
  • While target > arr[high]: low = high + 1, high = high * 2.
  • Run standard binary search between low and high.

Connected Patterns:

Find Position of Element in Sorted Array of Unknown SizeExponential SearchBinary Search on Answer

1. Linear Traversal

Intuition

Start at index 0 and increment index by 1 until arr[i] == target (return i) or arr[i] > target (return -1).

When to apply: When index p is guaranteed to be extremely small.

Algorithm

  1. Step 1: Set i = 0.
  2. Step 2: While arr[i] <= target, if arr[i] == target return i; else i++.
  3. Step 3: Return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int searchInfinite(const vector<int>& arr, int target) {
8 int i = 0;
9 while (arr[i] <= target) {
10 if (arr[i] == target) return i;
11 i++;
12 }
13 return -1;
14}
15
16int main() {
17 // Sample driver execution
18 cout << "Execution completed successfully." << endl;
19 return 0;
20}
21

Time & Space Complexity

  • Time complexity: O(p) — Takes p steps where p is the index of target.
  • Space complexity: O(1) — Only constant extra space.

2. Fixed Jump Search

Intuition

Advance high in jumps of k. When arr[high] >= target, linear scan the window [high - k, high].

When to apply: When memory access patterns benefit from block jumping.

Algorithm

  1. Step 1: Set step = 100, high = 0.
  2. Step 2: While arr[high] < target, high += step.
  3. Step 3: Linear scan from max(0, high - step) to high.
  4. Step 4: Return index or -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int searchJump(const vector<int>& arr, int target, int step = 100) {
8 int high = 0;
9 while (arr[high] < target) {
10 high += step;
11 }
12 int low = max(0, high - step);
13 for (int i = low; i <= high; ++i) {
14 if (arr[i] == target) return i;
15 if (arr[i] > target) return -1;
16 }
17 return -1;
18}
19
20int main() {
21 // Sample driver execution
22 cout << "Execution completed successfully." << endl;
23 return 0;
24}
25

Time & Space Complexity

  • Time complexity: O(p / k + k) — Takes p/k block jumps and at most k linear comparisons.
  • Space complexity: O(1) — Uses constant auxiliary space.

3. Exponential Doubling + Binary Search

Intuition

Initialize low = 0, high = 1. While arr[high] < target, update low = high + 1 and high = high * 2. Then perform regular binary search in [low, high].

When to apply: Optimal standard method for infinite/unknown-size sorted structures.

Algorithm

  1. Step 1: Initialize low = 0, high = 1.
  2. Step 2: While arr[high] < target: low = high + 1, high = high * 2.
  3. Step 3: Run standard binary search in [low, high]:
  4. - mid = low + (high - low) / 2.
  5. - If arr[mid] == target return mid.
  6. - If arr[mid] < target low = mid + 1, else high = mid - 1.
  7. Step 4: Return -1 if not found.

Trace for arr = [3, 5, 7, 9, 10, 90, 100, 130, 140, 160], target = 10

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1 (Range expansion): Start window [low=0, high=1]
Visual state
Values and pointers at this exact step
pointers
S
3
5
7
9
10
0
↑ low
1
↑ high
2
3
4
Check / comparison
arr[high]=arr[1]=5 < target 10 -> Expand window.
Decision / next transition
Set low = 2, high = 4.
Why this step matters

Step 1 (Range expansion): Start window [low=0, high=1]. arr[1]=5 < target 10. Double window: low = 2, high = 1 * 2 = 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int searchInfiniteOptimal(const vector<int>& arr, int target) {
8 int low = 0, high = 1;
9 while (arr[high] < target) {
10 low = high + 1;
11 high = high * 2;
12 }
13 while (low <= high) {
14 int mid = low + (high - low) / 2;
15 if (arr[mid] == target) return mid;
16 if (arr[mid] < target) low = mid + 1;
17 else high = mid - 1;
18 }
19 return -1;
20}
21
22int main() {
23 // Sample driver execution
24 cout << "Execution completed successfully." << endl;
25 return 0;
26}
27

Time & Space Complexity

  • Time complexity: O(log p) — Doubling bounds takes O(log p) steps. Binary search on a range of size O(p) takes O(log p) steps. Total time is O(log p).
  • Space complexity: O(1) — Requires only O(1) auxiliary pointers.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear TraversalO(p)O(1)Check elements sequentially from index 0.Inspects every single element up to p.
2.Fixed Jump SearchO(p/k + k)O(1)Jump in blocks of size k, then linear scan.Fixed step size is not adaptive.
3.Exponential Doubling + Binary SearchOptimalO(log p)O(1)Exponentially double high pointer to find interval, then binary search.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Target is at index 0 (low=0, high=1, found immediately).
  • Target is at index 1.
  • Target is smaller than arr[0] (return -1 immediately).
  • Target is not present in the array.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why linear search is O(p) whereas exponential doubling is O(log p).
  2. Show how doubling the index creates a range of size at most 2p, which binary search solves in log(2p) = O(log p).
  3. Discuss how to handle out-of-bounds sentinel values (e.g. Integer.MAX_VALUE).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does exponential doubling result in O(log p) complexity?

2.What is the initial search window in exponential doubling?

Back to DSA Sheet