Search target in unknown-length sorted array

Q: Search target in unknown-length sorted array

This question evaluates proficiency in algorithm design and analysis, focusing on efficient search under interface constraints, handling unknown-length sorted array-like structures, duplicate elements, and reasoning about time and space complexity.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a read-only, ascendingly sorted array-like interface of unknown length that exposes get(i) and returns +∞ (or a sentinel) when i is out of bounds, implement search(k) that returns the index of k or −1 if not present. Minimize the number of calls to get, handle duplicates by returning any valid index, and analyze time and space complexity.

Search target in unknown-length sorted array

Overview

Comments (0)