Search In A Sorted Array Of Unknown Size - Leetcode Solution

Problem Statement:

Given an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return -1. However, the array size 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 all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.

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

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

Solution:

The given problem statement is to search for an element in a sorted array of unknown size. A brute-force approach to solve the problem is to iterate through the array searching for the given target element. But as the array size is unknown, this approach doesn’t give optimum results. Therefore, we can use the Binary search approach to find the required element.

Algorithm:

1. We start by initializing two variables left and right to 0 and 1 respectively. Here, we are trying to find a range in which the target element exists in the array.

2. Iterate until target variable is greater than the element at the right index.

3. Assign the left variable to the right and update the right variable to twice the current value of the right variable.

4. When the target element is between the left and right indices, perform binary search to find the target element.

5. If the target element is not found, return -1.

6. If the target element is found, return its index.

Pseudo code:

int search(ArrayReader reader, int target) { int left=0; int right=1;

 while(reader.get(right)<target) {  
     left=right;
     right= 2* right;
 }

 while(left<=right) {
     int mid=(left + (right - left) / 2);

     if(reader.get(mid)==target){
         return mid;
     } else if(reader.get(mid)> target) {
         right=mid-1;
     } else {
         left=mid+1;
     }
 }
 return -1;

}

Complexity Analysis:

Time complexity: Since we are initially trying to find in which range the target element exists and that range will have at most 2 * log(n + 1) elements, the time complexity of this approach is O(log n) as we need to perform binary search in the range.

Space Complexity: With the given solution, we are not using any extra space, so the space complexity of this approach is O(1).

Therefore, the solution to the problem search in a sorted array of unknown size is to scan the unknown-size array's left and right indices and find the range within that the target element exists and then perform the binary search within that range to find the index of the target.

1