Jobs

Interviews

Discussions

Search in a Sorted Array of Unknown Size

Medium

Asked by:

17 views

Topics:

ArraysBinary Search

Given an integer array sorted in ascending order, nums, and an integer target, search in nums for the target. Since the size of nums is unknown to you, you may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0-indexed).

You may assume that all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.

Return the index of the target if it exists in the array; otherwise, return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

1 <= nums.length <= 10⁴
-9999 <= nums[i] <= 9999
All values of nums are unique.
nums is sorted in ascending order.
-9999 <= target <= 9999

Try coding it in LeetCode

Search in a Sorted Array of Unknown Size

Medium

Asked by:

17 views

Topics:

ArraysBinary Search

You may assume that all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.

Return the index of the target if it exists in the array; otherwise, return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

1 <= nums.length <= 10⁴
-9999 <= nums[i] <= 9999
All values of nums are unique.
nums is sorted in ascending order.
-9999 <= target <= 9999

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the return value of `reader.get(index)` when the index is out of bounds?
Can the integers in the array and the target integer be negative?
Is there a theoretical upper bound on the size of the array, even if I cannot directly determine it?
Can the `target` value appear multiple times in the array? If so, should I return the index of the first occurrence, or is any index acceptable?
What is the range of possible integer values within the array?

Brute Force Solution

Approach

We need to find a specific value within a collection that has an unknown size. The brute force way is to simply check every possible place in the collection, one by one, until we either find the value or determine it's not there. It's like looking for a specific book on a bookshelf of unknown length by checking each book individually.

Here's how the algorithm would work step-by-step:

Start by looking at the very first spot in the collection.
Check if the value in that spot is the value we are looking for.
If it is, we're done! We found it.
If it's not, move to the next spot in the collection.
Repeat the checking process: is this spot the value we want?
Keep moving and checking each spot, one after the other.
If we reach the end of the collection without finding the value, then the value isn't in the collection.

Code Implementation

def search_in_unknown_size_array_brute_force(array, target):
    index = 0

    # Iterate through the array until an error occurs
    while True:
        try:
            current_value = array[index]

            # We found our target so return the index
            if current_value == target:
                return index

            # If we went past the target then return -1
            if current_value > target:
                return -1

            index += 1

        # Array index out of bounds means element isn't present
        except IndexError:
            return -1

Big(O) Analysis

Time Complexity

O(n) – The provided solution performs a linear search through the collection. In the worst-case scenario, the target value is either at the very end of the collection or not present at all. In both cases, the algorithm has to iterate through all n elements of the collection. Therefore, the time complexity is directly proportional to the size of the collection, n, resulting in O(n) time complexity.

Space Complexity

O(1) – The provided algorithm only uses a constant amount of extra space. No auxiliary data structures like arrays, lists, or hash maps are used. The algorithm iterates through the collection, but it doesn't store any intermediate values or visited positions, meaning the space used does not depend on the size of the collection, N. Therefore, the space complexity is constant.

Optimal Solution

Approach

The problem is like finding a specific page in a very large book, but you don't know how many pages are in the book. The best way is to start by guessing further and further out until we go too far, then narrow down the search.

Here's how the algorithm would work step-by-step:

Start by checking a page that is a short distance away from the beginning.
If that page is smaller than what we are looking for, double the distance and try again.
Keep doubling the distance until the page is larger than what we're looking for, or we hit the end of the book.
Now that we know the range where the page must be, use a process of repeatedly dividing the range in half and checking the middle page.
If the middle page is too small, look in the half of the range after the middle page.
If the middle page is too large, look in the half of the range before the middle page.
Keep dividing the range in half until you find the exact page you were looking for, or the range is empty, meaning it's not in the book.

Code Implementation

def search_in_sorted_array_of_unknown_size(sorted_array, target_value):
    left_index = 0
    right_index = 1

    # Expand the search range until target_value is within.
    while sorted_array.get(right_index) is not None and sorted_array.get(right_index) < target_value:
        left_index = right_index
        right_index *= 2

    # Array size found or target > last element.
    while left_index <= right_index:
        middle_index = left_index + (right_index - left_index) // 2
        middle_value = sorted_array.get(middle_index)

        # Key value not present.
        if middle_value is None:
            right_index = middle_index - 1
            continue

        if middle_value == target_value:
            return middle_index

        # Adjust search based on comparison.
        if middle_value < target_value:
            left_index = middle_index + 1

        else:
            right_index = middle_index - 1

    # Target not found after binary search
    return -1

Big(O) Analysis

Time Complexity

O(log n) – The algorithm first exponentially searches to find the upper bound of the search space, which takes O(log n) time because the index doubles in each step. Once the upper bound is found, a binary search is performed within the determined range. Binary search repeatedly divides the search interval in half, also taking O(log n) time. Therefore, the overall time complexity is dominated by these two logarithmic operations, resulting in O(log n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It only needs to store a few variables like the start and end indices for the range in which we perform binary search. The space used by these variables does not depend on the size of the array, even though the algorithm explores further and further, the size of the array is not explicitly stored. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
reader is null or reader.get(0) returns out-of-bounds indicator	Return -1 immediately, indicating target not found.
Target is smaller than the first element in the array	Return -1 as the array is sorted and target cannot exist.
Target is larger than all elements in the (virtually sized) array	Binary search will eventually have left > right, and return -1 after exhausting search space defined by initial exponential search.
Target exists at index 0	Binary search should correctly identify index 0 during the search.
Array contains only one element which matches the target	The initial size estimate combined with binary search will quickly converge to the single element index if it matches the target.
Out-of-bounds indicator is a valid integer (e.g., INT_MAX)	Ensure we don't compare target to the out-of-bounds indicator directly in binary search to avoid unexpected results or overflow.
Integer overflow when calculating mid in binary search (left + right) / 2	Use left + (right - left) / 2 to prevent integer overflow when calculating the mid-point.
Target is present multiple times in the sorted array	Binary search may return any valid index where the target exists, and problem doesn't require a particular index.

reader is null or reader.get(0) returns out-of-bounds indicator

How to Handle:

Return -1 immediately, indicating target not found.

Target is smaller than the first element in the array

How to Handle:

Return -1 as the array is sorted and target cannot exist.

Target is larger than all elements in the (virtually sized) array

How to Handle:

Binary search will eventually have left > right, and return -1 after exhausting search space defined by initial exponential search.

Target exists at index 0

How to Handle:

Binary search should correctly identify index 0 during the search.

Array contains only one element which matches the target

How to Handle:

The initial size estimate combined with binary search will quickly converge to the single element index if it matches the target.

Out-of-bounds indicator is a valid integer (e.g., INT_MAX)

How to Handle:

Ensure we don't compare target to the out-of-bounds indicator directly in binary search to avoid unexpected results or overflow.

Integer overflow when calculating mid in binary search (left + right) / 2

How to Handle:

Use left + (right - left) / 2 to prevent integer overflow when calculating the mid-point.

Target is present multiple times in the sorted array

How to Handle:

Binary search may return any valid index where the target exists, and problem doesn't require a particular index.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the return value of `reader.get(index)` when the index is out of bounds?
Can the integers in the array and the target integer be negative?
Is there a theoretical upper bound on the size of the array, even if I cannot directly determine it?
Can the `target` value appear multiple times in the array? If so, should I return the index of the first occurrence, or is any index acceptable?
What is the range of possible integer values within the array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the very first spot in the collection.
Check if the value in that spot is the value we are looking for.
If it is, we're done! We found it.
If it's not, move to the next spot in the collection.
Repeat the checking process: is this spot the value we want?
Keep moving and checking each spot, one after the other.
If we reach the end of the collection without finding the value, then the value isn't in the collection.

Code Implementation

def search_in_unknown_size_array_brute_force(array, target):
    index = 0

    # Iterate through the array until an error occurs
    while True:
        try:
            current_value = array[index]

            # We found our target so return the index
            if current_value == target:
                return index

            # If we went past the target then return -1
            if current_value > target:
                return -1

            index += 1

        # Array index out of bounds means element isn't present
        except IndexError:
            return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by checking a page that is a short distance away from the beginning.
If that page is smaller than what we are looking for, double the distance and try again.
Keep doubling the distance until the page is larger than what we're looking for, or we hit the end of the book.
Now that we know the range where the page must be, use a process of repeatedly dividing the range in half and checking the middle page.
If the middle page is too small, look in the half of the range after the middle page.
If the middle page is too large, look in the half of the range before the middle page.
Keep dividing the range in half until you find the exact page you were looking for, or the range is empty, meaning it's not in the book.

Code Implementation

def search_in_sorted_array_of_unknown_size(sorted_array, target_value):
    left_index = 0
    right_index = 1

    # Expand the search range until target_value is within.
    while sorted_array.get(right_index) is not None and sorted_array.get(right_index) < target_value:
        left_index = right_index
        right_index *= 2

    # Array size found or target > last element.
    while left_index <= right_index:
        middle_index = left_index + (right_index - left_index) // 2
        middle_value = sorted_array.get(middle_index)

        # Key value not present.
        if middle_value is None:
            right_index = middle_index - 1
            continue

        if middle_value == target_value:
            return middle_index

        # Adjust search based on comparison.
        if middle_value < target_value:
            left_index = middle_index + 1

        else:
            right_index = middle_index - 1

    # Target not found after binary search
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
reader is null or reader.get(0) returns out-of-bounds indicator	Return -1 immediately, indicating target not found.
Target is smaller than the first element in the array	Return -1 as the array is sorted and target cannot exist.
Target is larger than all elements in the (virtually sized) array	Binary search will eventually have left > right, and return -1 after exhausting search space defined by initial exponential search.
Target exists at index 0	Binary search should correctly identify index 0 during the search.
Array contains only one element which matches the target	The initial size estimate combined with binary search will quickly converge to the single element index if it matches the target.
Out-of-bounds indicator is a valid integer (e.g., INT_MAX)	Ensure we don't compare target to the out-of-bounds indicator directly in binary search to avoid unexpected results or overflow.
Integer overflow when calculating mid in binary search (left + right) / 2	Use left + (right - left) / 2 to prevent integer overflow when calculating the mid-point.
Target is present multiple times in the sorted array	Binary search may return any valid index where the target exists, and problem doesn't require a particular index.

reader is null or reader.get(0) returns out-of-bounds indicator

How to Handle:

Return -1 immediately, indicating target not found.

Target is smaller than the first element in the array

How to Handle:

Return -1 as the array is sorted and target cannot exist.

Target is larger than all elements in the (virtually sized) array

How to Handle:

Binary search will eventually have left > right, and return -1 after exhausting search space defined by initial exponential search.

Target exists at index 0

How to Handle:

Binary search should correctly identify index 0 during the search.

Array contains only one element which matches the target

How to Handle:

The initial size estimate combined with binary search will quickly converge to the single element index if it matches the target.

Out-of-bounds indicator is a valid integer (e.g., INT_MAX)

How to Handle:

Ensure we don't compare target to the out-of-bounds indicator directly in binary search to avoid unexpected results or overflow.

Integer overflow when calculating mid in binary search (left + right) / 2

How to Handle:

Use left + (right - left) / 2 to prevent integer overflow when calculating the mid-point.

Target is present multiple times in the sorted array

How to Handle:

Binary search may return any valid index where the target exists, and problem doesn't require a particular index.