Leetcode 702. Search in a Sorted Array of Unknown Size

Problem Explanation

The problem deals with searching for a value in a sorted array in ascending order when the size of the array is unknown. The main stipulation is that the array size is unknown and you can only access the contents through the ArrayReader interface, where ArrayReader.get(k) returns the element of the array at the specified index. Other conditions given are ranging values of the integers and the out of bound return value for ArrayReader.get. Assuming we have an input of array = [-1,0,3,5,9,12], target = 9, we need to return the index of 9 which is 4.

The approach used to solve the problem is a Binary Search Algorithm. This is because the list is sorted making it efficient to divide and cut the search space in half during each iteration greatly reducing the time complexity to O(log n). You would find the middle of the search space, if the target value is less than the value at the current mid-point, adjust the right edge otherwise adjust the left.

For example, let's have an array = [-1,0,3,5,9,12], and the target is 9. We would start by setting our left and right pointers to 0 and 10,000 respectively since that's the minimum and maximum values in the array. Then, we would keep getting the middle index and comparing the element at that index with the target. If the target is less, we know it has to be on the left half of the middle index hence we adjust our right pointer to the middle. If the target is more, we know it is on the right half hence we adjust our left pointer to the middle plus one. This process continues until our left pointer is equal to or greater than the right. At that point, if the target is in the array, the left pointer would be pointing at it hence we can return the left pointer, if it isn't in the array, our left pointer would be pointing to an index with value greater than the target or an index that exceeds the array size. Hence we can return -1.

Solution in Python

1
2python
3class Solution:
4    def search(self, reader: 'ArrayReader', target: int) -> int:
5        left, right = 0, 10**4
6        while left <= right:
7            mid = (left+right) // 2
8            if reader.get(mid) == 2147483647 or reader.get(mid) > target:
9                right = mid - 1
10            elif reader.get(mid) < target:
11                left = mid + 1
12            else:
13                return mid
14        
15        return -1

Solution in Java

1
2java
3class Solution {
4    public int search(ArrayReader reader, int target) {
5        int left = 0;
6        int right = 10000;
7
8        while (left <= right) {
9            int mid = left + (right - left) / 2;
10            int num = reader.get(mid);
11            if (num == target) return mid;
12            if (num < target) {
13                left = mid + 1;
14            } else {
15                right = mid - 1;
16            }
17        }
18
19       
20        return -1;
21    }
22}

Solution in JavaScript

1
2javascript
3class Solution {
4  search(reader, target) {
5    let left = 0;
6    let right = 10000;
7  
8    while (left <= right) {
9      let mid  = Math.floor((right + left)/ 2)
10      let num = reader.get(mid)
11      if ( num == target) return mid;
12      if (num < target) {
13        left = mid + 1;
14      } else {
15        right = mid - 1;
16      }
17    }
18    return -1;
19  }
20}

Solution in C++

1
2cpp
3class Solution {
4public:
5    int search(ArrayReader& reader, int target) {
6        int l = 0;
7        int r = 10'000;
8
9        while (l < r) {
10            const int m = (l + r) / 2;
11            if (reader.get(m) >= target)
12                r = m;
13            else
14                l = m + 1;
15        }
16        return reader.get(l) == target ? l : -1;
17    }
18};

Solution in C#

1
2csharp
3public class Solution {
4    public int Search(ArrayReader reader, int target) {
5        int left = 0, right = 10000;
6        while (left <= right) 
7        {
8            int mid = left + (right - left) / 2;
9            if (reader.Get(mid) == target) return mid;
10            if (reader.Get(mid) > target) right = mid - 1;
11            else left = mid + 1;
12        }
13        return -1;
14    }
15}

In conclusion, the binary search algorithm is an efficient way of searching for values in sorted arrays especially when the size of the array is not known beforehand. Knowing that the array is sorted is what allows us to make the decision to discard the left or right half at each step.Other programming languages like Ruby, Go, Swift etc., can also utilize a similar binary search approach to solve the problem.

Solution in Ruby

1
2ruby
3class Solution
4  def search(reader, target)
5    left = 0
6    right = 10000
7
8    while left <= right
9      mid = (left + right) / 2
10      num = reader.get(mid)
11      if num == target
12        return mid
13      elsif num < target
14        left = mid + 1
15      else
16        right = mid - 1
17      end
18    end
19
20    return -1
21  end
22end

Solution in Go

1
2go
3func search(reader ArrayReader, target int) int {
4    left, right := 0, 10000
5    
6    for left <= right {
7        mid := (left + right) / 2
8        num := reader.get(mid)
9        if num == target {
10            return mid
11        } else if num < target {
12            left = mid + 1
13        } else {
14            right = mid - 1
15        }
16    }
17    
18    return -1
19}

Solution in Swift

1
2swift
3class Solution {
4    func search(_ reader: ArrayReader, _ target: Int) -> Int {
5        var left = 0, right = 10000
6        while left <= right {
7            let mid = (left + right) / 2
8            let num = reader.get(mid)
9            if num == target {
10                return mid
11            } else if num < target {
12                left = mid + 1
13            } else {
14                right = mid - 1
15            }
16        }
17        return -1
18    }
19}

Even in cases where the size of the array is unknown, the binary search algorithm proves to be a potent tool due to its denoted time complexity of O(log n). By iteratively reducing the search space and knowing that the array is sorted, you can reliably find a target value or establish the absence of it in the array. If the array were unsorted, a binary search could not be used, and a linear search approach would have to suffice elevating the time complexity to O(n).