Search in a Sorted Array of Unknown Size – Java Solution

Explore Other Solutions


/**
 * // This is ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface ArrayReader {
 *   public int get(int index) {}
 * }
 */

class Solution {
  public int search(ArrayReader reader, int target) {
    int l = 0;
    int r = 10000;

    while (l < r) {
      final int m = (l + r) / 2;
      if (reader.get(m) >= target)
        r = m;
      else
        l = m + 1;
    }

    return reader.get(l) == target ? l : -1;
  }
}

Problem Description

So, you think you can find a number in a sorted array of unknown size? Well, welcome to the club! Imagine you’re at a party, and you’re trying to find your friend who’s hiding somewhere in a massive crowd. You can’t see the end of the crowd, and you have no idea how many people are there. Sounds fun, right?

In this problem, you’re given an interface called ArrayReader that allows you to access elements in a sorted array, but you can’t just ask for the size of the array. Your task is to find a target number in this mysterious array. If you find it, great! If not, well, better luck next time!

Approach Explanation

The code uses a binary search approach to efficiently find the target number. It initializes two pointers, l and r, to represent the left and right bounds of the search space. The algorithm repeatedly narrows down the search space by checking the middle element. If the middle element is greater than or equal to the target, it moves the right pointer to the middle. Otherwise, it shifts the left pointer to the middle plus one. This process continues until the target is found or the search space is exhausted.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(log N)
Space Complexity	O(1)

Real-World Example

Imagine you’re searching for a specific book in a gigantic library where the shelves are endless. You can only see a few books at a time, and you have to keep asking the librarian (the ArrayReader) for the title of the book at a certain position. Using the binary search method, you can quickly narrow down the section of the library where your book might be hiding, instead of aimlessly wandering around.