Course contentsShow
← Computer Science
Lesson 818 of 2,87219. Searching and SelectionFree lesson

Binary Search on Infinite Arrays

Extend binary search to work on unbounded or very large arrays where the size is unknown.

Binary Search on Infinite Arrays

You'll learn how to apply binary search when you don't know the array's size or it's effectively unbounded.

The Challenge

Imagine you have a sorted array so enormous that accessing its length would be too expensive, or it's streaming in dynamically. Traditional binary search requires knowing the endpoints upfront—but what if you don't have that luxury?

The Core Idea

The trick is to find a suitable upper bound first, then apply standard binary search within that range.

Two-phase approach:

  1. Exponential search for bounds: Start at index 0 and keep doubling your position (1, 2, 4, 8, 16...) until you find a position where the value is greater than your target (or you hit the end). This gives you a range [left, right] where your target must live if it exists.

  2. Standard binary search: Once you've bounded the problem, run regular binary search between left and right.

Why Exponential Jumps?

Doubling the position grows exponentially (2⁰, 2¹, 2², 2³...), so you quickly cover vast distances. If the target is at position k, you'll find a suitable upper bound in just O(log k) steps—not O(k) steps!

The Process

Suppose you're searching for target = 50:

  • Check index 1, 2, 4, 8, 16... until arr[16] > 50 or you can't read further
  • Now you know target (if present) lies between indices 8 and 16
  • Apply binary search on that narrow range

Key Takeaway: Binary search on infinite arrays uses exponential probing to find bounds in O(log k) time, then standard binary search, making it efficient even when the array size is unknown or unbounded.