Find the position of an element in a sorted infinite array

Problem

Given an infinite sorted array (or an array with unknown size), find the index of a given target value if it is present in the array, otherwise return -1.

Examples

Example 1

Input: array = [2, 5, 7, 9, 10, 12, 15, 16, 18, 20, 24, 28, 32, 35], target = 16
Output: 7
Explanation: The target `16` is present at index `7` in the array.

Example 2

Input: array = [2, 5, 7, 9, 10, 12, 15, 16, 18, 20, 24, 28, 32, 35], target = 19
Output: -1
Explanation: The target `19` is not present in the array.

Solution

This problem is similar to [Exponential Search](/cs/algorithms/search/sorted/exponential-search).

Method 1 – Exponential Search with Binary Search

Intuition

Since the array is infinite (or size is unknown), we can't use its length for binary search. Instead, we first find a range where the target could be by exponentially increasing the upper bound (end), then perform binary search within that range.

Approach

1. Start with start = 0 and end = 1.
2. While target > arr[end], set start = end and double end (end *= 2).
3. Once target <= arr[end], perform binary search between start and end:
   • For each mid = (start + end) // 2, if arr[mid] == target, return mid.
   • If arr[mid] < target, set start = mid + 1.
   • If arr[mid] > target, set end = mid - 1.
4. If not found, return -1.

Code

C++

class Solution {
public:
	int findPosition(const vector<int>& arr, int target) {
		int start = 0, end = 1;
		while (arr[end] < target) {
			start = end;
			end *= 2;
		}
		while (start <= end) {
			int mid = start + (end - start) / 2;
			if (arr[mid] == target) return mid;
			else if (arr[mid] < target) start = mid + 1;
			else end = mid - 1;
		}
		return -1;
	}
};

Go

func findPosition(arr []int, target int) int {
	start, end := 0, 1
	for arr[end] < target {
		start = end
		end *= 2
	}
	for start <= end {
		mid := start + (end-start)/2
		if arr[mid] == target {
			return mid
		} else if arr[mid] < target {
			start = mid + 1
		} else {
			end = mid - 1
		}
	}
	return -1
}

Java

class Solution {
	public int findPosition(int[] arr, int target) {
		int start = 0, end = 1;
		while (arr[end] < target) {
			start = end;
			end *= 2;
		}
		while (start <= end) {
			int mid = start + (end - start) / 2;
			if (arr[mid] == target) return mid;
			else if (arr[mid] < target) start = mid + 1;
			else end = mid - 1;
		}
		return -1;
	}
}

Kotlin

class Solution {
	fun findPosition(arr: IntArray, target: Int): Int {
		var start = 0
		var end = 1
		while (arr[end] < target) {
			start = end
			end *= 2
		}
		while (start <= end) {
			val mid = start + (end - start) / 2
			if (arr[mid] == target) return mid
			else if (arr[mid] < target) start = mid + 1
			else end = mid - 1
		}
		return -1
	}
}

Python

class Solution:
	def find_position(self, arr: list[int], target: int) -> int:
		start, end = 0, 1
		while arr[end] < target:
			start = end
			end *= 2
		while start <= end:
			mid = start + (end - start) // 2
			if arr[mid] == target:
				return mid
			elif arr[mid] < target:
				start = mid + 1
			else:
				end = mid - 1
		return -1

Rust

impl Solution {
	pub fn find_position(arr: &[i32], target: i32) -> i32 {
		let (mut start, mut end) = (0, 1);
		while arr[end] < target {
			start = end;
			end *= 2;
		}
		while start <= end {
			let mid = start + (end - start) / 2;
			if arr[mid] == target {
				return mid as i32;
			} else if arr[mid] < target {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		-1
	}
}

TypeScript

class Solution {
	findPosition(arr: number[], target: number): number {
		let start = 0, end = 1;
		while (arr[end] < target) {
			start = end;
			end *= 2;
		}
		while (start <= end) {
			const mid = start + Math.floor((end - start) / 2);
			if (arr[mid] === target) return mid;
			else if (arr[mid] < target) start = mid + 1;
			else end = mid - 1;
		}
		return -1;
	}
}

Complexity

• ⏰ Time complexity: O(log p) — Exponential search finds the range in O(log p), then binary search finds the target in O(log p), where p is the position of the target.
• 🧺 Space complexity: O(1) — Only uses a constant amount of extra space.