Search in a Sorted Array of Unknown Size - Practice Coding Problems

Search in a Sorted Array of Unknown Size - Problem

This is an interactive problem. You have a sorted array of unique elements with an unknown size. You cannot directly access the array, but you can use the ArrayReader interface.

The ArrayReader.get(i) method:

Returns the value at index i (0-indexed) if i is within bounds
Returns 2³¹ - 1 if i is out of bounds

Given an integer target, return the index where the target exists in the hidden array, or -1 if it doesn't exist.

Constraint: Your algorithm must run in O(log n) time complexity.

Input & Output

Example 1 — Target Found

$ Input: secret = [-1,0,2,3,4], target = 2

› Output: 2

💡 Note: Target 2 is found at index 2. First we find bounds by checking indices 1→2→4, then binary search between indices 2 and 4.

Example 2 — Target Not Found

$ Input: secret = [-1,0,3,5,9,12], target = 2

› Output: -1

💡 Note: Target 2 is not in the array. We search through the bounds but don't find the target value.

Example 3 — Target at Beginning

$ Input: secret = [-1,0,3,5,9,12], target = -1

› Output: 0

💡 Note: Target -1 is found at index 0, the very first position in the array.

Constraints

1 ≤ secret.length ≤ 10⁴
-10⁴ ≤ secret[i], target ≤ 10⁴
secret is sorted in ascending order
secret consists of unique elements

Visualization

Tap to expand

Understanding the Visualization

Unknown Array

We have a sorted array but don't know its size

Interface

ArrayReader.get(i) returns element or 2³¹-1 if out of bounds

Goal

Find target index in O(log n) time

Key Takeaway

🎯 Key Insight: Use exponential doubling to find bounds, then binary search within those bounds for O(log n) complexity

Asked in

G Google 25 f Facebook 18 a Amazon 12 M Microsoft 8

The key insight is to first find the array bounds using exponential search (doubling indices: 1→2→4→8), then apply binary search within those bounds. This achieves the required O(log n) time complexity. The optimal approach uses two phases: boundary discovery and binary search. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n)	O(1)	Check each index sequentially until target is found or out of bounds
Find Bounds + Binary Search	O(log n)	O(1)	First find the array bounds by exponential search, then apply binary search

Linear Search — Algorithm Steps

Start at index 0
Check current position using reader.get()
If target found, return index; if out of bounds, return -1
Move to next index and repeat

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at index 0

Check

Compare each element with target

Result

Return index when found or -1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct {
    int* arr;
    int size;
} ArrayReader;

int get(ArrayReader* reader, int index) {
    if (index >= reader->size) {
        return INT_MAX;
    }
    return reader->arr[index];
}

int solution(ArrayReader* reader, int target) {
    int index = 0;
    while (1) {
        int val = get(reader, index);
        if (val == INT_MAX) {
            return -1;
        }
        if (val == target) {
            return index;
        }
        if (val > target) {
            return -1;
        }
        index++;
    }
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    ArrayReader reader = {arr, size};
    int result = solution(&reader, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In worst case, we check every element in the array sequentially

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for current index and value

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler